Home | | Design and Analysis of Algorithms | DijkstraŌĆÖs Algorithm

# DijkstraŌĆÖs Algorithm

In this section, we consider the single-source shortest-paths problem: for a given vertex called the source in a weighted connected graph, find shortest paths to all its other vertices.

DijkstraŌĆÖs Algorithm

In this section, we consider the single-source shortest-paths problem: for a given vertex called the source in a weighted connected graph, find shortest paths to all its other vertices. It is important to stress that we are not interested here in a single shortest path that starts at the source and visits all the other vertices. This would have been a much more difficult problem (actually, a version of the traveling salesman problem introduced in Section 3.4 and discussed again later in the book). The single-source shortest-paths problem asks for a family of paths, each leading from the source to a different vertex in the graph, though some paths may, of course, have edges in common.

A variety of practical applications of the shortest-paths problem have made the problem a very popular object of study. The obvious but probably most widely used applications are transportation planning and packet routing in communi-cation networks, including the Internet. Multitudes of less obvious applications include finding shortest paths in social networks, speech recognition, document formatting, robotics, compilers, and airline crew scheduling. In the world of enter-tainment, one can mention pathfinding in video games and finding best solutions to puzzles using their state-space graphs (see Section 6.6 for a very simple example of the latter).

There are several well-known algorithms for finding shortest paths, including FloydŌĆÖs algorithm for the more general all-pairs shortest-paths problem discussed in Chapter 8. Here, we consider the best-known algorithm for the single-source shortest-paths problem, called DijkstraŌĆÖs algorithm.4 This algorithm is applicable to undirected and directed graphs with nonnegative weights only. Since in most ap-plications this condition is satisfied, the limitation has not impaired the popularity of DijkstraŌĆÖs algorithm.

DijkstraŌĆÖs algorithm finds the shortest paths to a graphŌĆÖs vertices in order of their distance from a given source. First, it finds the shortest path from the source to a vertex nearest to it, then to a second nearest, and so on. In general, before its ith iteration commences, the algorithm has already identified the shortest paths to i ŌłÆ 1 other vertices nearest to the source. These vertices, the source, and the edges of the shortest paths leading to them from the source form a subtree Ti of the given graph (Figure 9.10). Since all the edge weights are nonnegative, the next vertex nearest to the source can be found among the vertices adjacent to the vertices of Ti. The set of vertices adjacent to the vertices in Ti can be referred to as ŌĆ£fringe verticesŌĆØ; they are the candidates from which DijkstraŌĆÖs algorithm selects the next vertex nearest to the source. (Actually, all the other vertices can be treated as fringe vertices connected to tree vertices by edges of infinitely large weights.) To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u, the sum of the distance to the nearest tree vertex v (given by the weight of the edge (v, u)) and the length dv of the shortest path from the source to v (previously determined by the algorithm) and then selects the vertex with the smallest such sum. The fact that it suffices to compare the lengths of such special paths is the central insight of DijkstraŌĆÖs algorithm.

To facilitate the algorithmŌĆÖs operations, we label each vertex with two labels. The numeric label d indicates the length of the shortest path from the source to this vertex found by the algorithm so far; when a vertex is added to the tree, d indicates the length of the shortest path from the source to that vertex. The other label indicates the name of the next-to-last vertex on such a path, i.e., the parent of the vertex in the tree being constructed. (It can be left unspecified for the source s and vertices that are adjacent to none of the current tree vertices.) With such labeling, finding the next nearest vertex uŌłŚ becomes a simple task of finding a fringe vertex with the smallest d value. Ties can be broken arbitrarily.

After we have identified a vertex uŌłŚ to be added to the tree, we need to perform two operations:

Move uŌłŚ from the fringe to the set of tree vertices. For each remaining fringe vertex u that is connected to uŌłŚ by an edge of weight w(uŌłŚ, u) such that duŌłŚ + w(uŌłŚ, u) < du, update the labels of u by uŌłŚ and duŌłŚ + w(uŌłŚ, u), respectively. Figure 9.11 demonstrates the application of DijkstraŌĆÖs algorithm to a specific graph.

The labeling and mechanics of DijkstraŌĆÖs algorithm are quite similar to those used by PrimŌĆÖs algorithm (see Section 9.1). Both of them construct an expanding subtree of vertices by selecting the next vertex from the priority queue of the remaining vertices. It is important not to mix them up, however. They solve different problems and therefore operate with priorities computed in a different manner: DijkstraŌĆÖs algorithm compares path lengths and therefore must add edge weights, while PrimŌĆÖs algorithm compares the edge weights as given.

Now we can give pseudocode of DijkstraŌĆÖs algorithm. It is spelled outŌĆö in more detail than PrimŌĆÖs algorithm was in Section 9.1ŌĆöin terms of explicit operations on two sets of labeled vertices: the set VT of vertices for which a shortest path has already been found and the priority queue Q of the fringe vertices. (Note that in the following pseudocode, VT contains a given source vertex and the fringe contains the vertices adjacent to it after iteration 0 is completed.)

ALGORITHM     Dijkstra(G, s)

//DijkstraŌĆÖs algorithm for single-source shortest paths

//Input: A weighted connected graph G =  V , E  with nonnegative weights

and its vertex s

//Output: The length dv of a shortest path from s to v

// and its penultimate vertex pv for every vertex v in V Initialize(Q) //initialize priority queue to empty

for every vertex v in V

dv ŌåÉ Ōł×;        pv ŌåÉ null

Insert(Q, v, dv) //initialize vertex priority in the priority queue ds ŌåÉ 0; Decrease(Q, s, ds) //update priority of s with ds

VT ŌåÉ Ōłģ

for i ŌåÉ 0 to |V | ŌłÆ 1 do

uŌłŚ ŌåÉ DeleteMin(Q)          //delete the minimum priority element

VT ŌåÉ VT Ōł¬ {uŌłŚ}

for every vertex u in V ŌłÆ VT that is adjacent to uŌłŚ do if duŌłŚ + w(uŌłŚ, u) < du

du ŌåÉ duŌłŚ + w(uŌłŚ, u);           pu ŌåÉ uŌłŚ

Decrease(Q, u, du)

The time efficiency of DijkstraŌĆÖs algorithm depends on the data structures used for implementing the priority queue and for representing an input graph itself. For the reasons explained in the analysis of PrimŌĆÖs algorithm in Section 9.1, it is The shortest paths (identified by following nonnumeric labels backward from a destination vertex in the left column to the source) and their lengths (given by numeric labels of the tree vertices) are as follows: FIGURE 9.11 Application of DijkstraŌĆÖs algorithm. The next closest vertex is shown in bold.

in  \$(|V |2) for graphs represented by their weight matrix and the priority queue implemented as an unordered array. For graphs represented by their adjacency lists and the priority queue implemented as a min-heap, it is in O(|E| log |V |). A still better upper bound can be achieved for both PrimŌĆÖs and DijkstraŌĆÖs algorithms if the priority queue is implemented using a sophisticated data structure called the Fibonacci heap (e.g., [Cor09]). However, its complexity and a considerable overhead make such an improvement primarily of theoretical value.

Exercises 9.3

Explain what adjustments if any need to be made in DijkstraŌĆÖs algorithm and/or in an underlying graph to solve the following problems.

Solve the single-source shortest-paths problem for directed weighted graphs.

Find a shortest path between two given vertices of a weighted graph or digraph. (This variation is called the single-pair shortest-path problem.)

Find the shortest paths to a given vertex from each other vertex of a weighted graph or digraph. (This variation is called the single-destination shortest-paths problem.)

Solve the single-source shortest-paths problem in a graph with nonnegative numbers assigned to its vertices (and the length of a path defined as the sum of the vertex numbers on the path).

Solve the following instances of the single-source shortest-paths problem with vertex a as the source: Give a counterexample that shows that DijkstraŌĆÖs algorithm may not work for a weighted connected graph with negative weights.

Let T be a tree constructed by DijkstraŌĆÖs algorithm in the process of solving the single-source shortest-paths problem for a weighted connected graph G.

True or false: T is a spanning tree of G?

True or false: T is a minimum spanning tree of G?

Write pseudocode for a simpler version of DijkstraŌĆÖs algorithm that finds only the distances (i.e., the lengths of shortest paths but not shortest paths themselves) from a given vertex to all other vertices of a graph represented by its weight matrix.

Prove the correctness of DijkstraŌĆÖs algorithm for graphs with positive weights.

Design a linear-time algorithm for solving the single-source shortest-paths problem for dags (directed acyclic graphs) represented by their adjacency lists.

Explain how the minimum-sum descent problem (Problem 8 in Exercises 8.1) can be solved by DijkstraŌĆÖs algorithm.

Shortest-path modeling Assume you have a model of a weighted connected graph made of balls (representing the vertices) connected by strings of appro-priate lengths (representing the edges).

Describe how you can solve the single-pair shortest-path problem with this model.

Describe how you can solve the single-source shortest-paths problem with this model.

Revisit the exercise from Section 1.3 about determining the best route for a subway passenger to take from one designated station to another in a well-developed subway system like those in Washington, DC, or London, UK. Write a program for this task.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Introduction to the Design and Analysis of Algorithms : Greedy Technique : DijkstraŌĆÖs Algorithm |

Related Topics