Using the dijkstra's algorithm find the shortest path from node c to node f, shown in the attached graph.:confused:

Any help would be greatly appreciated!

Printable View

- Jan 4th 2008, 04:42 AM*skywalker*dijkstra's algorithm
Using the dijkstra's algorithm find the shortest path from node c to node f, shown in the attached graph.:confused:

Any help would be greatly appreciated! - Jan 6th 2008, 11:16 AM3leggeddogDijkstra's Algorithm
Ok, so first, here's the steps that you follow in Dijkstra's algorithm.

First, identify your starting node. In your example, this is node c.

Next, identify all nodes that are "reachable" from node c. These are nodes b and d.

Choose the node with the "least expensive" edge. In this case, it is (c,d), which has a "cost" of 4.

Now, nodes c and d are both in the set of nodes that have permanent distances.

Your next goal is to look for nodes that are reachable from any node that has already has a permanent distance. Here is one of the main keys to the algorithm - if you're going from a node that is already in the permanent set to a node that is not (let's call them i and j, respectively), the total distance traveled is (permanent distance of i + distance from i to j). You need to remember to update the distances at each step. In this case, the distance from c to b is still 6, while the distance from d to a is (4+10=14) and the distance from d to e is (4+1=5). The cheapest distance of these sets is 5, so add e to the permanent set.

This process repeats itself. I really recommend going to this website

Dijkstra's Shortest Path Algorithm

and using the applet there to see how the rest of the steps work. You just draw in your graph, and it will step through it in a very understandable way. I've also included a file with the solution to this problem.