Indian Computing Olympiad

Shortest paths

Single-source shortest paths: Dijkstra's algorithm

The CMI travel desk insists that on booking tickets only on the national carrier, which has an obscure pricing policy. The cheapest way between two cities may not correspond to the most direct route.

For instance, suppose we have cities connected by flights as below (where 1 is CMI) with the cost of each direct flight is shown along the edge.

                    700
                3 ------ 4
        800   / |
            /   | 60
          /     |             500
         1------2 ------ 5 --------- 6
           100      200    \       /
                         100 \   / 50
                               7
      

The goal is to find the cheapest route to every other city.

This is called the "Single source shortest path problem". Here is an algorithm to solve this problem, due to Edsger Dijkstra.

A good way to think of this problem is to imagine that there are petrol tanks at each node, with edges corresponding to pipelines connecting the tanks whose length is given by the cost of the edge. We set fire to the first tank and the fire spreads at a uniform rate along all pipelines. If this rate is 1 unit length per second, the time at which a tank burns corresponds to the shortest path to that tank. Here is an algorithm to systematically compute the next tank that will explode at each step.

We use a modified version of BFS.

Initially, we mark the currently known distance from the start vertex to each vertex. This is 0 for start vertex, infinity everywhere else. We also mark whether a vertex is visited or not. Initially, no vertex is visited.

Initially

      Vertex     1     2     3     4     5     6     7
      Distance   0    inf   inf   inf   inf   inf   inf
      Visited    0     0     0     0     0     0     0
      

Pick an unvisited vertex with the currently lowest distance to process next (this is the tank that will next explode). In this case it is 1. Visit 1 and update distances to all its neighbours.

      Vertex     1     2     3     4     5     6     7
      Distance   0    100   800   inf   inf   inf   inf
      Visited    1     0     0     0     0     0     0
      

Now, 2 is the smallest unvisited vertex, so we visit 2 and update distances to all its neighbours. The distance to 3 reduces to 160 (via 2) and distance to 5 becomes 300.

      Vertex     1    2     3     4     5     6     7
      Distance   0    100   160   inf   300   inf   inf
      Visited    1     1     0     0     0     0     0
      

Now, 3 is smallest unvisited vertex, so we explore it next and update distance to 4.

      Vertex     1     2     3     4     5     6     7
      Distance   0    100   160   860   300   inf   inf
      Visited    1     1     1     0     0     0     0
      

Now, 5 is smallest, so we explore it next and update distance to 6 and 7.

      Vertex     1     2     3     4     5     6     7
      Distance   0    100   160   860   300   800   400
      Visited    1     1     1     0     1     0     0
      

Now, 7 is smallest, so we explore it next and update distance to 6.

      Vertex     1     2     3     4     5     6     7
      Distance   0    100   160   860   300   450   400
      Visited    1     1     1     0     1     0     1
      

Now, 6 is smallest, so we explore it, but no further updates.

      Vertex     1     2     3     4     5     6     7
      Distance   0    100   160   860   300   450   400
      Visited    1     1     1     0     1     1     1
      

Finally, we visit 4.

      Vertex     1     2     3     4     5     6     7
      Distance   0    100   160   860   300   450   400
      Visited    1     1     1     1     1     1     1
      

At this point, we have computed shortest paths from 1 to all other vertices.

Implementation

We use two arrays, ExpectedBurnTime and Burnt.

Initially,

• ExpectedBurnTime[1] = 0;
• ExpectedBurnTime[i] = infinity, for i other than 1
  (Use a sufficiently large value, say the sum of all the weights in the graph)
• Burnt[i] = 0, for all i

In each round:

• Among all unburnt vertices, pick j with minimum ExpectedBurnTime. (Initially, this is 1 since Burnt[i] = 0 for all i and only ExpectedBurnTime[1] is not infinity
• Set Burnt[j] = 1.
• Update ExpectedBurnTime[k] for each neighbour k of j, if necessary.

What is the complexity of Dijkstra's algorithm?

• Each round fixes the shortest path to one more vertex, so there are n rounds
• In each round, we pick the unmarked vertex with the smallest value, mark it and update values for its neighbours.
• Finding the smallest unmarked vertex takes time n
• Updating neighbours takes time n if we use an adjacency matrix.

So, the overall cost is n².

Video lectures on Single-source shortest paths: Dijkstra's algorithm, NPTEL online course on Design and Analysis of Algorithms

• Dijkstra's algorithm (Lecture slides)

• Analysis of Dijkstra's algorithm (Lecture slides)