Click here to Skip to main content
14,599,201 members
Rate this:
Please Sign up or sign in to vote.
See more:
I have a dijkstra algorithm for weighted, undirected graph. How can I rearrange it in order to calculate weighted and directed graph's shortest path?
Posted
Updated 19-May-11 5:07am
v2

1 solution

Rate this:
Please Sign up or sign in to vote.

Solution 1

You have more than enough information on this well-known algorithm to implement it in C++. See http://en.wikipedia.org/wiki/Dijkstra's_algorithm[^].

Now, this article does not mention arc weights. You can easily modify the algorithm if you need to take it into account. Look at the distance calculation in the pseudocode (see dist, dist_between). When you calculate them, multiply each arc's distance with its weight, that's all you need.

—SA
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100