# shortest path, graph problem

Page 1 of 1

## 4 Replies - 763 Views - Last Post: 03 November 2012 - 11:08 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=298471&amp;s=23ed9a8996e5ad157c98c569fa4a4484&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 oha055

• D.I.C Regular

Reputation: 49
• 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

• D.I.C Lover

Reputation: 203
• Posts: 1,717
• 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?

### #3 oha055

• D.I.C Regular

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

## Re: shortest path, graph problem

Posted 03 November 2012 - 10:13 AM

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

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11790
• Posts: 44,309
• 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.

### #5 oha055

• D.I.C Regular

Reputation: 49
• 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

Page 1 of 1

 .related ul{list-style-type:circle;font-size:12px;font-weight:bold;}.related li{margin-bottom:5px;background-position:left 7px!important;margin-left:-35px;}.related h2{font-size:18px;font-weight:bold;}.related a{color:blue;}