4 Replies - 549 Views - Last Post: 03 November 2012 - 11:08 AM Rate Topic: -----

#1 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 49
  • View blog
  • Posts: 273
  • Joined: 02-February 09

shortest path, graph problem

Posted 03 November 2012 - 09:23 AM

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


Is This A Good Question/Topic? 0
  • +

Replies To: shortest path, graph problem

#2 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • View blog
  • Posts: 1,693
  • Joined: 13-March 10

Re: shortest path, graph problem

Posted 03 November 2012 - 10:02 AM

Is just shortest path problem you are trying to solve or all-pairs shortest path?
Was This Post Helpful? 0
  • +
  • -

#3 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 49
  • View blog
  • Posts: 273
  • Joined: 02-February 09

Re: shortest path, graph problem

Posted 03 November 2012 - 10:13 AM

View Postdarek9576, 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 :)
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10823
  • View blog
  • Posts: 40,354
  • Joined: 27-December 08

Re: shortest path, graph problem

Posted 03 November 2012 - 10:36 AM

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.
Was This Post Helpful? 1
  • +
  • -

#5 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 49
  • View blog
  • Posts: 273
  • Joined: 02-February 09

Re: shortest path, graph problem

Posted 03 November 2012 - 11:08 AM

Ok, thank you for your reply! :) I will try to implement a solution based on this algorithm then :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1