# Shortest path in an undirected and complete graph

• (2 Pages)
• 1
• 2

## 15 Replies - 2345 Views - Last Post: 27 August 2012 - 11:30 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=290002&amp;s=f6aa12b693688c5b53bb06e7c66b19dd&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 Skydiver

• Code herder

Reputation: 2037
• Posts: 6,064
• Joined: 05-May 12

## Re: Shortest path in an undirected and complete graph

Posted 27 August 2012 - 11:30 AM

blackcompe, on 26 August 2012 - 01:35 AM, said:

2. This paper (pg. 14) gives an algorithm for finding the optimal Hamiltonian path, although it's a little tough to decipher.

What little of if I can decipher indicates that you have to pick a node 'p' as the final node, and then apply the algorithm. But what if I picked a bad 'p'? So that then means that I need to do the algorithm V-1 times to make sure that I picked the best 'p' or find a better 'p'.

So given lines 3-4 already show this:
```for s = 1 to N-2
for i,j = 1 to N

```

This looks like O(n3) to me. Doing another loop to try out all the possible p's would bring this algorithm up to O(n4). Am I missing something?

Still beats O(n!), though.

This post has been edited by Skydiver: 27 August 2012 - 11:30 AM