[oha055]

Since this is not a question of implementation, this may not be the right place to post my question, so feel free to move it.

So, an assignment requires me to find a shortest path in a weighted undirected graph. Does anyone happen to know which is the best algorithm for this particular task? I have looked into Dijkstra's algorithm but it seems to only focus on directed graphs (would this algorithm still be the best approach?).

Any thougths on this is greatly appreciated!

This post has been edited by oha055: 03 November 2012 - 09:25 AM

[darek9576]

Is just shortest path problem you are trying to solve or all-pairs shortest path?

[oha055]

darek9576, on 03 November 2012 - 06:02 PM, said:

Is just shortest path problem you are trying to solve or all-pairs shortest path?

Just a single shortest path

[macosxnerd101]

With Dijkstra's algorithm, you do have an undirected graph. I can see where you are getting confused though. With Dijkstra's algorithm, the same vertex could be visited twice. Picture the following Graph:

A -- B --- E -- F
   / |     |
  /  |     |
C    D --- G

When you go from A, you put B's unvisited edges into a priority queue. So B-C, B-D, and B-E. When you go from D-G and G-E, you shouldn't revisit the E-B edge.

[oha055]

Ok, thank you for your reply! I will try to implement a solution based on this algorithm then