i58 / Introduction to Graph Theory
5.4 Shortest path problems
Let Gbe a connectedledge-weightedgraph. Then ashortest path problem
is a
in which we have to find a path betweentwo vertices uand vin C. Such prkden
that t
weights of the edges ofthe pathis minimum. The weight of the shortest path is
the shortest distance between uandv. Here, the graph Gmay be undirected, , calt
or mixed. The shortest path problem1is also known as the single-pair
problem.
shortestdirectpatAh
There are several types of shortest path problems. Three typés of ssuch
are given below: problems
() The single-source shortest path problems: The problem of findingtthe shortes
path from asource vertex to remaining all the vertices in the graph Gis
the single-source shortest path problem. Thesingle-source shortest path called
can be solved usng Dijkstras algorithm. We can use Bellman-}Ford's
problets
edge-weights are negative.
algorithm if
() The single-destination shortest path problems: The problem of finding the shoe
est path from every vertex to asingle destination vertex in a digraph Dis know a
the single-destination shortest path problem. Reversing the edge-direction in th
digraph D, the problem can be converted to the single-source shortest path proble
So, we can solve this problem using Dijkstras algorithm.
(ii) A-pairs shortest path problem: The problem of finding shortest path betweem
every pair of vertices in a graph Gis known as the all-pairs shortest path problem
This type of problems can be solved using Floyd-Warshall's algorithm or johnsons
algorithm.
5.4.1 Dijkstras algorithm
In 1956, Edsger Wybe Dijkstra (1l May 1930-6 August 2002), a Dutch computer
scientist was working as aprogrammer at the mathematical centre in Amsterdam. Ia
order to demonstrate the capabilities of a new computer that is known as ARMAG
'hewas thinking about the shortest path problems. During this period, he designed
a shortest path algorithm. In 1959, an article on this algorithm was published by
Dijkstra. The shortest path algorithm designed by Dijkstra is known as Dijkstras
algorithm. It is asingle-source shortest path algorithm, which is applicable to the
connected graphs having non-negative weights of its edges. It plays very impora
role in several areas of networking,. The algorithm is given below:
Dijkstra'salgorithm
Step I. Mark all unvisited vertices and create a set S of all these unvisited vertice.
Ch 5. Tree 159
I. Assign to every vertex (v) atentative distance value l(). Set it to zero
Ar the. sourte vertex s and to infinity for remaining vertices in S, i.e., 1($) =0 and
()= forv*s. Set the initial vertex as current.
Rteo ll. Let tbe the destination vertex in S. IfV(u) be minimom for i eS and u = t,
Step IV. For all edge e = {u,v} incident with u, let v e S.Then replace l(v) by
min ("), I(») +a(e)).
Sep V. Replace Sby S- {u} and go to the step II.
Note S.1. Before applying the Dijkstras algorithm, remove all loops and parallel
sdges leaving only the edge with smallest weight if the graph contains loops and
perallel edges.
Theorem S.19. Let in Dijkstra'salgorithm, l(v) be finite corresponding to the vertex
Tt Some stage. Then there exists a path from the source vertex s to vwith length
().
Ezample 5.15. Let us consider the following undirected graph with source vertexs:
10
2
d
Fig. 5.10
NOw, we would like to find the shortest path fromn the single saurce s to all the
vertices of the graph.
tep 1. The initial labelling:
Vertex (v) b C d t
I(")
S {s, 4, b, c, d, t}
tep I1. For u=s, l(s) = 0, which is
minimum.
Dtep ll. There existsstwo edges,
that a, c S namely {s, a} and (s, c) incident with u =s. Observe
e! and l(a) =oo >4=0+4 =l(s) +w({5, a}). Then I(a)
will be replaced
160/ Introduction to Graph Theory
by 4. Bysimilar argument I(c) will be replaced by 2. Consequently, S b
for the next step.
sS-{)
Otep IV. Labelling:
Vertex (v) d
I(v) 0 4 2
S-{s} { a, b, c, d, t}
Qtep V. For u c, I(c) =2, which is minimum andceS-{s}.
Otep VI. There exists three edges, namely (c, a}, {c, b} and {c,d} incident with
uc, where a, b, deS- {s).
Observe that I(a) =4>3=2+1=I()+w({c, a}).Thus, I(a) will be replaced
by 3.
Again, 1(b) = o0 >10 =2+8 = I(c) + w({c, b})and I(d) = 0 >12 =2+10 =
I(c) +w({c, d} ).
i.1(6) and I(a) willbe replaced by 10 and 12 respectively. Consequently, the
unvisited vertex-set becomes S -{5, c}.
Step VIl. Labelling:
Vertex (v) s b c d
I(+) 0 3 10 2 12
S-{5,c) { a, b, d, t}
Qtep VI. For u =a, I(a) =3, which is minimum and a ¬S- {5, c}.
Qtep Ix. There exists exactly one edge, namely (a, b} incident with u= 4, where
bes-(s,c}. We see that I(b) =10 >8 =3+5= I(a) + w({a, b}). Thus, I(b) will
be replaced by 8and the unvisited vertex-set will become S-{s,c, a}, ie., {b, d, t}.
Otep x. Labelling:
Vertex (v) b c d
I() 0 3 8 2 12
S- {5,c, a}| { b, d, t)
Otep XI. For u b, I(b) - 8, which is minimum and b eS -{s,c, a).
Qtep XI1. There exists two edges, namely {b, d} and (b, t} incident with u = b
where d, teS- (5,c, a). Observe that I(d) = 12 > 8+2 = I(b) + w({b, d}) and
I() 0 >8+7= 1(b) + w({6, t}).
:.I(d) and(t) will bereplaced by 10 and 15 respectively andthe unvisited vertex
twill become S- (s,c, a, b), Le., (d, t}.
Ch5. Tree 161
gtep X 1 . Labelling:
Vertex (v) $ a b c d
I(v) 0 3 8 2 10 15
|S-(s,c, a, b) d, t)
Otep XIV. For u d, I(d) 10, which is minimum and d e S- {s, c, a, b}.
Ao XV. There exists only one edge, namely {d, t) incident with d, wherete
s-(5,,a, b}. Again, I() =15 > 10 + 3 1(d) + w({d, t)), which suggests to
replace I(1) by 13. Then the unvisited vertex-set becomes S -(s, c, a, b, d}.
gtep XVI. Labelling:
Vertex (v) S a bc d
I(v) 03 8 2 10 13
S-{s,c, a, b, d} { t}
Step XVII. u =t; stop.
Hence, the lengths of the shortest paths from the source vertex s to a, b, c, d and t
ae 3, 8, 2, 10 and 13 respectively.
We may cxpress the above process in the following compact form:
Vertex (v) a bc d
Step I(s) 1(a) (6) I(c) 1(d) i()
2
0
4
2
|S8 8 8
8
{5, a, b, c, d, t}
{a, b, c, d, t}
3 10 12 8
{a, b, d, t}
4 12 8
{b, d, t)
10 15 {d, t}
6 13 {}
Hence, the lengths of the shortest paths from the source vertex S to the vertices
4,b, c,d and t are 3,8, 2, 10 and 13 respectively.
zample 5.16. Using Dijkstras algorithm, find the shortest paths between the source
Vertlex sand every vertex of the following digraph:
muo. to Graph Theory - 11
162/ Introduction to Graph Theory
Fig. 5.11
Solutiog: Using Dijkstras algorithm on the given digraph, we obtain the following
table in which the lengths of the shortest paths between the source vertex s and every
vertex of the digrah are boxed:
Vertex (v) C d
S
Step I(s) (a) I(b) I(c) I(d) 1(e)
{s, a, b, c, d,e)
1 6 4 {a, b, c, d, e}
3 4 6 4 7 {b,c, d, e)
4 6 4 7 {e, d, e}
5 7 {c,e}
6 7 fe}
Hence,the lengths of the shortest paths from the source vertex s to the vertices
a, b,c, d and e are 1,4, 6,4 and 7 respectively. The paths are given in thefollowing
figure.
Fig. 5.12
Example 5.17,Using IDijkstras algorithm, find the shortest paths between the source
vertex s and every vertex of the following mixed graph:
Ch 5. Tree | 163
Fig. 5.13
solution: Using Dijkstras algorithm on the given mixed graph, we obtain the follow-
table in which the lengths of the shortest paths between the source vertex s and
ing
vertex oftthe mixed graph are boxed:
every
Vertex (v) C d
S
Step I(s) I(a) 1(b) I(c) 1(d)
{s, a, b, c, d}
2 2 6 4 {a, b, c, d}
3 6 4 {b,c, d}
4 6
{b, c}
5
{b}
.the lengths of the shortest paths fromn the source vertex s to all other vertices
4b,c and dare 2, 8, 6and4 respectivly. The paths are given in the following figure:
d
4
b
Fig. 5.14
Ezample 5.18. Usingg Dijkstras algorithm, find the shortest paths from every vertex
asingle destination vertex s in the following digraph D:
164 . Introduction to Graph Theory
Fig. 5.15
Solutiog: Reversing the edge-directions, we obtain a digraph given in Fig. 5.11. Then
using Dijkstras algorithm on it, we get SD table given in example 5.16. Observe that
the shortest distance of s from a, b, c, d and e ar¹ respectively 1, 4; 6, 4, 7.
The shortest paths in the modified graph are given in Fig. 5.12. Therefore,
reversing
the edge-directions of these paths, we get the required shortest paths shown in the
following figure.
Fig. 5.16
5.4.2 Floyd-Warshall's algorithm
In 1962, the Floyd-Warshall's algorithm was introduced independently by two Ame
ican computer scientists, Robert WFloyd (8 June 1936-25 September 2001) and
Stephen Warshall(15 November 1935-1lDecember 2006): though it was essenttauy
the same algorithm as published in 1959 by Bernard Roy (15 March 1934-28 October
2017), a French mathematician. This algorithm is also known as Floyd's algoritnn
Roy- Floyd's algorithm or Roy-Warshall's algorithm.
