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^{2}.

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)

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky