After each iteration, we pick the unvisited vertex with the least path length.

So we choose 5
before 7

Notice how the rightmost vertex has its path length updated twice

Repeat until all the vertices have been visited

Djikstra's algorithm pseudocode

We need to maintain the path distance of every vertex. We can store that in an array of size v,
where v is the number of vertices.

We also want to be able to get the shortest path, not only know the length of the shortest path.
For this, we map each vertex to the vertex that last updated its path length.

Once the algorithm is over, we can backtrack from the destination vertex to the source vertex to
find the path.

A minimum priority queue can be used to efficiently receive the vertex with least path distance.
function dijkstra(G, S)

for each vertex V in G distance[V] <- infinite previous[V] <- NULL

If V != S, add V to Priority Queue Q distance[S] <- 0

while Q IS NOT EMPTY

U <- Extract MIN from Q

for each unvisited neighbour V of U

tempDistance <- distance[U] + edge_weight(U, V) if tempDistance < distance[V]

distance[V] <- tempDistance previous[V] <- U

return distance[], previous[]

Dijkstra's Algorithm Complexity

Time Complexity: O(E Log V)

where, E is the number of edges and V is the number of vertices. Space Complexity: O(V)

Floyd Warshall Algorithm

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of
vertices in a weighted graph. This algorithm works for both the directed and undirected weighted
graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in
a cycle is negative).

A weighted graph is a graph in which each edge has a numerical value associated with it.

Floyd-Warhshall algorithm is also called as Floyd's algorithm, Roy-Floyd algorithm, Roy-

Warshall algorithm, or WFI algorithm.

This algorithm follows the dynamic programming approach to find the shortest paths.

How Floyd-Warshall Algorithm Works?

Let the given graph be:

Initial graph

Follow the steps below to find the shortest path between all the pairs of vertices.

Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the column
are indexed as i and j respectively. i and j are the vertices of the graph.

Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is no path
from ith vertex to jth vertex, the cell is left as infinity.

Fill each cell with the distance between ith and jth vertex

Now, create a matrix A1 using matrix A0. The elements in the first column and the first row are
left as they are. The remaining cells are filled in the following way.

Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is
the first vertex. A[i][j] is filled with (A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).

That is, if the direct distance from the source to the destination is greater than the path h the
vertex k, then the cell is filled with A[i][k] + A[k][j].

In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex

through this vertex k. Calculate the distance from the source vertex to destination
vertex through this vertex k

For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum of the distance
from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7.

Since 4 < 7, A0[2, 4] is filled with 4.

Similarly, A2 is created using A1. The elements in the second column and the second row are
left as they are.

In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in step

2. Calculate the distance from the source vertex to destination vertex through this vertex 2

Similarly, A3 and A4 is also created.

Calculate the distance from the source vertex to destination vertex

through this

vertex Calculate the distance from the source vertex to destination vertex through this vertex 4

A4 gives the shortest path between each pair of vertices.

Floyd-Warshall Algorithm

n = no of vertices

A = matrix of dimension n*n for k = 1 to n

for i = 1 to n for j = 1 to n

Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j]) return A

Time Complexity

There are three loops. Each loop has constant complexities. So, the time complexity of the
Floyd- Warshall algorithm is O(n3).

Network Flow

Flow Network is a directed graph that is used for modeling material Flow. There are two
different vertices; one is a source which produces material at some steady rate, and another one
is sink which consumes the content at the same constant speed. The flow of the material at any
mark in the system is the rate at which the element moves.

Some real-life problems like the flow of liquids through pipes, the current through wires and
delivery of goods can be modelled using flow networks.

Definition: A Flow Network is a directed graph G = (V, E) such that

For each edge (u, v) ∈ E, we associate a nonnegative weight capacity c (u, v) ≥ 0.If (u, v) ∉ E,
we assume that c (u, v) = 0.

There are two distinguishing points, the source s, and the sink t;

For every vertex v ∈ V, there is a path from s to t containing v.

Let G = (V, E) be a flow network. 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 x V→R such that the following properties hold:

Play Video

Capacity Constraint: For all u, v ∈ V, we need f (u, v) ≤ c (u, v).

Skew Symmetry: For all u, v ∈ V, we need f (u, v) = - f (u, v).

Flow Conservation: For all u ∈ V-{s, t}, we need

The quantity f (u, v), which can be positive or negative, is known as the net flow from vertex u to
vertex v. In the maximum-flow problem, we are given a flow network G with source s and sink t,
and

a flow of maximum value from s to t.Ford-Fulkerson Algorithm

Initially, the flow of value is 0. Find some augmenting Path p and increase flow f on each edge
of p by residual Capacity cf (p). When no augmenting path exists, flow f is a maximum flow.

FORD-FULKERSON METHOD (G, s, t)

Initialize flow f to 0

while there exists an augmenting path p

do argument flow f along p

Return f

FORD-FULKERSON (G, s, t)

for each edge (u, v) ∈ E [G]

do f [u, v] ← 0

3. f [u, v] ← 0

while there exists a path p from s to t in the residual network Gf.

do cf (p)←min?{ Cf (u,v):(u,v)is on p}

for each edge (u, v) in p

do f [u, v] ← f [u, v] + cf (p)

8. f [u, v] ←-f[u,v]

Example: Each Directed Edge is labeled with capacity. Use the Ford-Fulkerson algorithm to find
the maximum flow.
Solution: The left side of each part shows the residual network Gf with a shaded augmenting
path p,and the right side of each part shows the net flow f.
Maximum Bipartite Matching

The bipartite matching is a set of edges in a graph is chosen in such a way, that no two edges in
that set will share an endpoint. The maximum matching is matching the maximum number of
edges.

When the maximum match is found, we cannot add another edge. If one edge is added to the
maximum matched graph, it is no longer a matching. For a bipartite graph, there can be more
than one maximum matching is possible.

Algorithm

bipartiteMatch(u, visited, assign)

Input: Starting node, visited list to keep track, assign the list to assign node with another node.

Output − Returns true when a matching for vertex u is possible.

Begin

for all vertex v, which are adjacent with u, do if v is not visited, then

mark v as visited

if v is not assigned, or bipartiteMatch(assign[v], visited, assign) is true, then assign[v] := u

return true done

return false End

maxMatch(graph) Input − The given graph.

Output − The maximum number of the match.

Begin

initially no vertex is assigned count := 0

for all applicant u in M, do make all node as unvisited

if bipartiteMatch(u, visited, assign), then increase count by 1

done End