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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.