Dijkstra's Algorithm

Can someone explain the steps of using this algorithm to me in as simple terms as possible? Successive Googling has left me totally confused.

Thanks.

Reply 1

mrmanps

this algorithm is fairly straight forward.

see this link for a practical illustration

http://www.mathsnet.net/asa2/2004/d12dijkstra.html

Reply 2

PlaystationStudies

I'll tell you how to apply Dijkstra's to the graph that mrmanps linked.

With Dijkstra's, the aim is to find the shortest path from one node to another. The first node is often A, but in the example it is S.

Preliminary step:

You’ll notice that each node has a little box drawn next to it, with three different cells that you can write stuff in.

Top-right cell: ‘Permanent label’ or ‘final label’. In this cell you write down the distance from node S to whatever node you’re at. Right now you’re at node S, so what’s the distance from node S to node S? That’s right, 0. So the first thing you want to do is to write 0 into the top-right cell.

Top-left cell: ‘Order of labelling’. In this cell you write down how many nodes you’ve ‘permanently labelled’ so far. How many nodes have you permanently labelled so far? That’s right, 1. So write 1 into the top-left cell.

Bottom cell: ‘Temporary label’. We’ll come to this in a moment…

Okay, down to the algorithm:

Step 1: You’ve just permanently labelled a node. Have a look at the arcs that are connecting this node to nodes that aren’t yet permanently labelled. What is the distance from S to these nodes? Write this value into the ‘temporary label’ cell.

In the example graph: You’ve just permanently labelled the start node. Have a look at the arcs that are connecting S to nodes that don’t yet have permanent labels. These are nodes A and B. The distance between S and A is 34, so write 34 into A’s temporary label cell. The distance between S and B is 22, so write 22 into B’s temporary label cell.

Step 2: Have a look at all of the nodes that don’t have permanent labels but do have temporary labels, including nodes that you temporarily labelled earlier. Which has the smallest value? Permanently label that node with that number. Go back to step 1.

In the example graph: Which node has the smallest temporary label value? B does (22). So write 22 into the ‘permanent label’ cell, and write 2 into the ‘order of labelling’ cell (remember, you write 2 here because this is the second node you’ve permanently labelled.

That’s all you need to know, but I’ll just do a few more steps so that you definitely get it.

Hints:

The stuff in this paragraph relates to step 1. You’ve just permanently labelled B. Have a look at the arcs connecting B to nodes that aren’t yet permanently labelled. These are nodes E and F. The distance from S to E is 43 (because 21 + 22 = 43) and the distance from S to F is 56. That’s step 1 completed again.

The stuff in this paragraph relates to step 2. Have a look at all the temporary labels, including nodes you temporarily labelled earlier! You’ll notice that node A has the smallest temporary label. So permanently label A. 34 goes into the ‘permanent label’ cell, and 3 goes into the ‘order of labelling’ cell.

Now repeat step 1, and keep going!

Remember, with Dijkstra’s algorithm you aren’t simply following a path. You might follow lots of different paths before finding the path of minimum weight, so don’t be concerned if you have to keep going back on yourself. This is how Dijkstra’s works.

Hope that helps.