Unit IV

Graph Algorithms: Bellman - Ford Algorithm; Single source shortest

paths in a DAG; Dijikstra’s algorithm, Johnson’s Algorithm for sparse
graphs; Flow networks and Ford- Fulkerson method; Maximum bipartite
matching.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 1

Shortest path Algorithms
• Relaxation
• The shortest path algorithms use the technique of relaxation.
• For each vertex v ꞓ V, we maintain an attribute d[v], which is an upper bound on
the weight of a shortest path from source s to v. We call d[v] a shortest-path
estimate.
• We initialize the shortest-path estimates and predecessors by the following
procedure.
• INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v ꞓ V[G]
2 do d[v] ← ∞
π[v] ← NIL
3 d[s] ← 0
After initialization,
predecessors π[v] = NIL for all v ꞓ V
d[s] = 0
and d[v] = ∞ for v ꞓ V - {s}. 2

Dr.P.V.Bhat, NMAMIT, Nitte

20-12-2023
• The process of relaxing an edge (u, v) consists of testing whether we
can improve the shortest path to v found so far by going through u
and, if so, updating d[v] and π[v].
• A relaxation step may decrease the value of the shortest-path esti-
mate d[v] and update v's predecessor field π[v].
• The following code performs a relaxation step on edge (u, v).
• RELAX(u, v, w)
if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
π[v] ← u
In Dijkstra's algorithm and the shortest-paths algorithm for directed
acyclic graphs, each edge is relaxed exactly once. In the Bellman-Ford
algorithm, each edge is relaxed many times.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 3

Single-source shortest paths in directed acyclic graphs
• By relaxing the edges of a weighted dag (directed acyclic graph)
G = (V, E) according to a topological sort of its vertices, we can
compute shortest paths from a single source in Θ(V + E) time.
• Shortest paths are always well defined in a dag, since even if there are
negative-weight edges but not to negative-weight cycles.
• The algorithm starts by topologically sorting the dag to impose a
linear ordering on the vertices.
• If there is a path from vertex u to vertex v, then u precedes v in the
topological sort. We make just one pass over the vertices in the
topologically sorted order.
• As we process each vertex, we relax each edge that leaves the vertex.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 4

Algorithm for Single-source shortest paths in DAG

• DAG-SHORTEST-PATHS(G, w, s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G, s)
3 for each vertex u, taken in topologically sorted order
4 do for each vertex v Adj[u]
5 do RELAX(u, v, w)

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 5

Nodes ∏(v)
r Nil
t S
X s
Y x
Z y
The execution of Single-source shortest paths DAG algorithm for a given graph

7
Nodes ∏(v)
r Nil
t S
20-12-2023
X s
Dr.P.V.Bhat, NMAMIT, Nitte
Y x
Z y
• The execution of the algorithm for shortest paths in a directed acyclic
graph is shown in previous slide.
• The vertices are topologically sorted from left to right.
• The source vertex is s.
• The d values are shown within the vertices
• (a) The situation before the first iteration of the for loop of lines 3-5.
• (b)-(g) The situation after each iteration of the for loop of lines 3-5.
The newly blackened vertex in each iteration was used as u in that
iteration. The values shown in part (g) are the final values.
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 8
Dijkstra's algorithm
• Dijkstra's algorithm solves the single-source shortest-paths problem
on a weighted, directed graph G = (V, E) for the case in which all edge
weights are nonnegative.
• Therefore, we assume that w(u, v) ≥ 0 for each edge (u, v) ꞓ E.
• With a good implementation, the running time of Dijkstra's algorithm
is lower than that of the Bellman Ford algorithm.
• Dijkstra's algorithm maintains a set S of vertices whose final shortest-
path weights from the source s have already been determined.
• The algorithm repeatedly selects the vertex u ꞓ {V – S} with the
minimum shortest-path estimate, adds u to S, and relaxes all edges
leaving u.
• In the following implementation, we use a min-priority queue Q of
vertices, keyed by their d values.
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 9
Dijkstra's algorithm
• DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2S←Ø
3 Q ← V[G]
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q)
6 S ← S Union {u}
7for each vertex v ꞓ Adj[u]
8 do RELAX(u, v, w)

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 10

Working of algorithm
• Dijkstra's algorithm relaxes edges.
• Line 1 performs the usual initialization of d and π values,
• line 2 initializes the set S to the empty set.
• The algorithm maintains the invariant that Q = V - S at the start of each
iteration of the while loop of lines 4- 8.
• Line 3 initializes the min-priority queue Q to contain all the vertices in V ;
since S = Ø at that time, the invariant is true after line 3. Each time through
the while loop of lines 4-8, a vertex u is extracted from Q = V - S and added
to set S, thereby maintaining the invariant.
• Vertex u, therefore, has the smallest shortest-path estimate of any vertex
in V - S. Then, lines 7-8 relax each edge (u, v) leaving u, thus updating the
estimate d[v] and the predecessor π[v] if the shortest path to v can be
improved by going through u.
• Observe that vertices are never inserted into Q after line 3 and that each
vertex is extracted from Q and added to S exactly once, so that the while
loop of lines 4-8 iterates exactly |V| times.
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 13
The execution of Dijkstra's algorithm- An example

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 14

• The source s is the leftmost vertex.
• The shortest-path estimates are shown within the vertices, and
shaded edges indicate predecessor values.
• Black vertices are in the set S, and white vertices are in the min-
priority queue Q = V - S.
• (a) The situation just before the first iteration of the while loop of
lines 4-8. The shaded vertex has the minimum d value and is chosen
as vertex u in line 5.
• (b)-(f) The situation after each successive iteration of the while loop.
The shaded vertex in each part is chosen as vertex u in line 5 of the
next iteration.
• The d and π values shown in part (f) are the final values. Because
Dijkstra's algorithm always chooses the "lightest" or "closest" vertex
in V - S to add to set S, we say that it uses a greedy strategy.
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 15
Bellman-Ford algorithm
• The Bellman-Ford algorithm solves the single-source shortest-paths
problem in the general case in which edge weights may be negative.
• Given a weighted, directed graph G = (V, E) with source s and weight
function w : E → R, the Bellman-Ford algorithm returns a boolean
value indicating whether or not there is a negative-weight cycle that is
reachable from the source.
• If there is such a cycle, the algorithm indicates that no solution exists.
If there is no such cycle, the algorithm produces the shortest paths
and their weights.
• The algorithm uses relaxation, progressively decreasing an estimate
d[v] on the weight of a shortest path from the source s to each vertex
v ꞓ V until it achieves the actual shortest-path weight δ(s, v).
• The algorithm returns TRUE if and only if the graph contains no
negative weight cycles that are reachable from the source.
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 16
Bellman-Ford algorithm
• BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i ← 1 to |V[G]| - 1
3 do for each edge (u, v) ꞓ E[G]
4 do RELAX(u, v, w)
5 for each edge (u, v) ꞓ E[G] do
6 if d[v] > d[u] + w(u, v) then
7 return FALSE
8 return TRUE

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 17

 Dr.P.V.Bhat, NMAMIT, Nitte 18
20-12-2023
 19
Dr.P.V.Bhat, NMAMIT, Nitte
20-12-2023
An example showing the working of algorithm

20
• In this particular example, each pass relaxes the edges in the order
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y).

Dr.P.V.Bhat, NMAMIT, Nitte

20-12-2023
The execution of the Bellman-Ford algorithm on a graph
• After initializing the d and π values of all vertices in line 1, the algorithm makes
|V| - 1 passes over the edges of the graph.
• Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each
edge of the graph once. Figures (b)-(e) show the state of the algorithm after each
of the four passes over the edges.
• After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return
the appropriate boolean value.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 21

• The source is vertex s.
• The d values are shown within the vertices, and shaded edges
indicate predecessor values: if edge (u, v) is shaded, then π[v] = u.
• In this particular example, each pass relaxes the edges in the order
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y).
• (a) The situation just before the first pass over the edges.
• (b)-(e) The situation after each successive pass over the edges.
• The d and π values in part (e) are the final values.
• The Bellman-Ford algorithm returns TRUE in this example.
• The Bellman-Ford algorithm runs in time O(V E), since the
initialization in line 1 takes Θ(V) time, each of the |V| - 1 passes over
the edges in lines 2-4 takes Θ(E) time, and the for loop of lines 5-7
takes O(E) time.
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 22
Johnson's algorithm for sparse graphs
• Johnson's algorithm finds shortest paths between all pairs in O(V2 lg V + V
E) time.
• For sparse graphs, it is asymptotically better than either repeated squaring
of matrices or the Floyd-Warshall algorithm.
• Johnson's algorithm uses as subroutines both Dijkstra's algorithm and the
Bellman-Ford algorithm
• Johnson's algorithm uses the technique of reweighting, which works as
follows.
• If all edge weights w in a graph G = (V, E) are nonnegative, we can find
shortest paths between all pairs of vertices by running Dijkstra's algorithm
once from each vertex
• If G has negative-weight edges but no negative-weight cycles, we simply
compute a new set of nonnegative edge weights that allows us to use the
same method.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 23

• The new set of edge weights must satisfy two important properties.
• 1. For all pairs of vertices u, v ꞓ V, a path p is a shortest path from u to
v using weight function w if and only if p is also a shortest path from u
to v using weight function w’.
• 2. For all edges (u, v), the new weight w’(u,v) is nonnegative.

• Where h(u) and h(v) are shortest cost from new vertex s considered
which is initialized wih a weight 0 to all vertices
• We use δ to denote shortest-path weights derived from weight
function w and δ’ to denote shortest-path weights derived from
weight function w’

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 24

 Johnson’s Algorithm
JOHNSON(G)
1 compute G′, where V[G′] = V[G]U {s},
E[G′] = E[G] U {(s, v) : v V[G]}, and
w(s, v) = 0 for all v ꞓ V[G]
2 if BELLMAN-FORD(G′, w, s) = FALSE
3 then print "the input graph contains a negative-weight cycle"
4 else
for each vertex v ꞓ V[G′]
5 do set h(v) to the value of δ(s, v) computed by the Bellman-Ford algorithm
6 for each edge (u, v) ꞓ E[G′]
7 do
8 for each vertex u ꞓ V[G]
9 do run DIJKSTRA(G, , , u) to compute for all v ꞓ V[G]
10 for each vertex v ꞓ V[G]
11 do
12 return D
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 26
Example

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 27

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 28
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 29
Explanation of figure

20-12-2023 30
Dr.P.V.Bhat, NMAMIT, Nitte
Flow networks
• A flow network G = (V, E) is a directed graph in which each edge (u, v)€ E
has a nonnegative capacity c(u, v) ≥ 0 with 2 special vertices a source s
and a sink t.
• If (u, v) E, we assume that c(u, v) = 0.
• We distinguish two vertices in a flow network: a source s and a sink t.
For convenience, we assume that every vertex lies on some path from
the source to the sink.
• That is, for every vertex v € V, there is a path The graph is therefore
connected, and |E| ≥ |V | - 1

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 31

Example for flow network

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 32

• Let G = (V, E) be a flow network with a capacity function c. Let s be the
source of the network, and let t be the sink.
• A flow in G is a real-valued function f : V × V → R that satisfies the following
three properties:
1. Capacity constraint: For all u, v € V, we require f (u, v) ≤ c(u, v).
2. Skew symmetry: For all u, v € V, we require f (u, v) = - f (v, u).
3. Flow conservation: For all u € V - {s, t}, we require

The quantity f (u, v), which can be integer is called the flow from vertex u to
vertex v. The value of a flow f is defined as

that is, the total flow out of the source. (Here, the |·| notation denotes flow
value, not absolute value)
In the maximum-flow problem, we are given a flow network G with source
s and sink t, and we wish to find a flow of maximum value.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 33

About properties
• The capacity constraint simply says that the flow from one vertex to
another must not exceed the given capacity.
• Skew symmetry is a notational convenience that says that the flow
from a vertex u to a vertex v is the negative of the flow in the reverse
direction.
• The flow-conservation property says that the total flow out of a
vertex other than the source or sink is 0. That is incoming load is
equal to out going load in every internal vertices.

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 34

Example for flow network with flow

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 35

Examples for flow network with flow

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 36

Residual network and augmenting path
• Residual network : Given a flow network and a flow, the residual network
consists of edges that can admit more flow.
• Suppose that we have a flow network G = (V, E) with source s and sink t. Let f
be a flow in G, and consider a pair of vertices u, v € V. The amount of
additional flow we can push from u to v before exceeding the capacity c(u, v)
is the residual capacity of (u, v), given by

• For example, if c(u, v) = 16 and f(u, v) = 11, then we can increase f(u, v) by
cf (u, v) = 5 units before we exceed the capacity constraint on edge (u, v).
• Augmenting path: Given a flow network G = (V, E) and a flow f, an
augmenting path p is a simple path from s to t in the residual network Gf. By
the definition of the residual network, each edge (u, v) on an augmenting
path admits some additional positive flow from u to v without violating the
capacity constraint on the edge

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 37

 Ford-Fulkerson method :
for solving the maximum-flow problem
• In the maximum-flow problem, we are given a flow network G with
source s and sink t, and we wish to find a flow of maximum value.
• FORD-FULKERSON(G, s, t)
1. for each edge (u, v) € E[G]
2. do f[u, v] ← 0
3. f[v, u] ← 0
4. while there exists a path p from s to t in the residual network G f
5. do cf(p) ← min {cf(u, v) : (u, v) is in p}
6. for each edge (u, v) in p
7. do f[u, v] ← f[u, v] + cf (p)
8. f[v, u] ← -f[u, v]
20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 38
Find maximum flow in the flow network using Ford-Fulkerson method

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 39

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 40
Find maximum flow in the flow network using
Ford-Fulkerson method

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 41

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 42
Find maximum flow in the flow network using Ford-Fulkerson method

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 43

20-12-2023 Dr.P.V.Bhat, NMAMIT, Nitte 44
T