Network algorithms 2. Shortest paths

Question 1

What is Dijkstra’s algorithm?

Answer 1

Dijkstra’s algorithm finds the shortest path between two nodes in an undirected algorithm.

Question 2

How is the working for Dijkstra’s algorithm shown?

Answer 2

The working is shown in boxes drawn at each node which will contain the following information:

Top left box - Order of permanent labelling

Top right box - Permanent label (shortest distance)

Bottom box - Temporary labels (working values)

Question 3

How do you carry out Dijkstra’s algorithm?

Answer 3

1. Label the start vertex with permanent label 0 and order label 1
2. Assign temporary labels to all the vertices that can be reached directly from the start
3. Select the vertex with the smallest temporary label and make its label permanent. Add the correct order label.
4. Put temporary labels on each vertex that can be reached directly from the vertex you have just made permanent. The temporary label must be equal to the sum of the permanent label and the direct distance from it. If there is an existing temporary label at a vertex, it should be replaced only if the new sum is smaller.
5. Select the vertex with the smallest temporary label and make its label permanent. Add the correct order label.
6. Repeat until the finishing vertex has a permanent label.
7. To find the shortest paths(s), trace back from the end vertex to the start vertex. Write the route forwards and state the length.

Question 4

What complexity does Dijkstra’s algorithm have?

Answer 4

Dijkstra’s algorithm has complexity O(n^2), where n is the number of nodes.