Shortest Paths
CHAPTER 4
NETWORK ALGORITHM
4.1 SHORTEST PATHS
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition
Shortest Paths
Shortest Paths
The shortest path between
what is the shortest path two vertices is a path with
between two vertices? the shortest length (least
number of edges)
▪ In a graph, edges are labeled with weights (or distances) and a source vertex
• Given a graph G = (V, E), a weighting function w(e), w(e) > 0, for the edges of G, and
a source vertex, v0. • We wish to determine a shortest path from v0 to vn
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition
Shortest Paths
Shortest Paths Problem
the single-source shortest path problem requires finding the shortest paths between a given source and
all other vertices
single-pair shortest finding the shortest path between given a
path problem source and a given destination vertex
all-pair shortest path finding the shortest paths between all
problem pairs of vertices
Example of shortest path problem for weighted graph
d c Shortest path from a to c?
1 Length of (a-b-c)=11
2 e 5 Length of (a-e-c)=10
9 2
Length of (a-b-e-c)=9
a b ∴Shortest path from a to c: (a-b-e-c)=9
6
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition
Shortest Paths
Dijkstra Algorithm
Shortest Path Algorithm
1. Set m = 1 and label vertex a with (−, 0) (the “−” represents a blank).
2. Check each edge e = (p, q) from some labeled vertex p to some unlabeled vertex q.
Suppose p’s labels are [r, d(p)]. If d(p) + k(e) = m, label q with (p, m).
3. If all vertices are not yet labeled, increment m by 1 and go to Step 2. Otherwise go to
Step 4. If we are only interested in a shortest path to z, then we go to Step 4 when z is
labeled.
4. For any vertex y, a shortest path from a to y has length d(y), the second label of y. Such
a path may be found by backtracking from y (using the first labels) as described below
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition
Shortest Paths
Dijkstra Algorithm
- This algorithm gives shortest paths from a given vertex a to all other vertices.
- Let k(e) denote the length of edge e. Let the variable m be a “distance counter.”
- For increasing values of m, the algorithm labels vertices whose minimum distance from
vertex a is m.
- The first label of a vertex x will be the previous vertex on the shortest path from a to x.
The second label of x will be the length of the shortest path from a to x
the previous vertex on the the length of the shortest
shortest path from a to x path from a to x
[r, d(p)]
(p, q) (p, m), where d(p) + k(e) = m.
Example b(A, 2)
A(−, 0) 2 3
c(b, 5)
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition
Dijkstra Algorithm Shortest Paths
Example
A newly married couple, upon finding that they are incompatible, want to find a shortest
path from point N (Niagara Falls) to point R (Reno) in the road network shown in Figure.
By applying shortest path algorithm,
f (N, 10)
4 10
i (f, 14) N (−, 0)
m (j, 19)
6 4
6 8 2
5 6 e (d, 11)
2 d (c, 7)
4
j (k, 17) 3 b (N, 2)
R (m, 24) 2 3
12 3 2
5 g (h, 13)
4
c (b, 5)
k (h, 14) 5 6
20 h (d, 9)
Shortest Path: N–b–c–d–h–k–j–m–R with length 24
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition
Shortest Paths
Floyd’s algorithm
Let matrix D have entry dij = ∞ (or a very large number) if there is no edge from the ith
vertex to the jth vertex; otherwise dij is the length of the edge from xi , to x j . Then
Floyd’s algorithm is most easily stated with the following deceptively simple computer
program:
FOR k← 1 TO n DO
FOR i ← 1 TO n DO
FOR j← 1 TO n DO
IF 𝑑𝑖𝑘 + 𝑑𝑘𝑗 < 𝑑𝑖𝑗 THEN 𝑑𝑖𝑗 ← 𝑑𝑖𝑘 + 𝑑𝑘𝑗 ;
When finished, 𝑑𝑖𝑗 will be the shortest distance from the ith
vertex to the jth vertex.
Section 4.1, Alan Tucker, Applied Combinatorics 6th edition