GRAPH

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes
also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph.
More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is
denoted by G(E, V).

Graph Terminology
Path

A path can be defined as the sequence of nodes that are followed in order to reach some terminal
node V from the initial node U.

Closed Path

A path will be called as closed path if the initial node is same as terminal node. A path will be closed
path if V0=VN.

Simple Path

If all the nodes of the graph are distinct with an exception V 0=VN, then such path P is called as closed
simple path.

Cycle

A cycle can be defined as the path which has no repeated edges or vertices except the first and last
vertices.

Connected Graph

A connected graph is the one in which some path exists between every two vertices (u, v) in V. There
are no isolated nodes in connected graph.

Complete Graph
A complete graph is the one in which every node is connected with all other nodes. A complete graph
contain n(n-1)/2 edges where n is the number of nodes in the graph.

Weighted Graph

In a weighted graph, each edge is assigned with some data such as length or weight. The weight of an
edge e can be given as w(e) which must be a positive (+) value indicating the cost of traversing the
edge.

Digraph

A digraph is a directed graph in which each edge of the graph is associated with some direction and
the traversing can be done only in the specified direction.

Loop

An edge that is associated with the similar end points can be called as Loop.

Adjacent Nodes

If two nodes u and v are connected via an edge e, then the nodes u and v are called as neighbours or
adjacent nodes.

Degree of the Node

A degree of a node is the number of edges that are connected with that node. A node with degree 0
is called as isolated node.

Representation of Graphs
While representing graphs, we must carefully depict the elements (vertices and edges) present in the
graph and the relationship between them. Pictorially, a graph is represented with a finite set of nodes
and connecting links between them.

A graph is a data structure that consist a sets of vertices (called nodes) and edges. There are two ways
to store Graphs into the computer's memory:

o Sequential representation (or, Adjacency matrix representation)

o Linked list representation (or, Adjacency list representation)

Adjacency Matrix
The Adjacency Matrix is a V×V matrix where the values are filled with either 0 or 1. If the link exists
between Vi and Vj, it is recorded 1; otherwise, 0.

For the given graph below, let us construct an adjacency matrix −

The adjacency matrix is −

Adjacency List
The adjacency list is a list of the vertices directly connected to the other vertices in the graph.

The adjacency list is –

Operations of Graphs
The primary operations of a graph include creating a graph with vertices and edges, and displaying
the said graph. However, one of the most common and popular operation performed using graphs
are Traversal, i.e. visiting every vertex of the graph in a specific order.

There are two types of traversals in Graphs −

 Depth First Search Traversal

 Breadth First Search Traversal

Depth First Search Traversal

Depth First Search is a traversal algorithm that visits all the vertices of a graph in the decreasing order
of its depth. In this algorithm, an arbitrary node is chosen as the starting point and the graph is
traversed back and forth by marking unvisited adjacent nodes until all the vertices are marked.

The DFS traversal uses the stack data structure to keep track of the unvisited nodes.

Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a stack to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F
and lastly to C. It employs the following rules.
  Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.

 Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the
vertices from the stack, which do not have adjacent vertices.)

 Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

Step Traversal Description

1 Initialize the stack.

Mark S as visited and put it onto the

stack. Explore any unvisited adjacent
node from S. We have three nodes
2
and we can pick any of them. For this
example, we shall take the node in an
alphabetical order.

Mark A as visited and put it onto the

stack. Explore any unvisited adjacent
3 node from A. Both S and D are
adjacent to A but we are concerned
for unvisited nodes only.
 Visit D and mark it as visited and put
onto the stack. Here, we
have B and C nodes, which are
4
adjacent to D and both are unvisited.
However, we shall again choose in an
alphabetical order.

We choose B, mark it as visited and

put onto the stack. Here B does not
5
have any unvisited adjacent node. So,
we pop B from the stack.

We check the stack top for return to

the previous node and check if it has
6
any unvisited nodes. Here, we
find D to be on the top of the stack.

Only unvisited adjacent node is

7 from D is C now. So we visit C, mark it
as visited and put it onto the stack.
As C does not have any unvisited adjacent node so we keep popping the stack until we find a node
that has an unvisited adjacent node. In this case, there's none and we keep popping until the stack is
empty.

Breadth First Search Traversal

Breadth First Search is a traversal algorithm that visits all the vertices of a graph present at one level
of the depth before moving to the next level of depth. In this algorithm, an arbitrary node is chosen
as the starting point and the graph is traversed by visiting the adjacent vertices on the same depth
level and marking them until there is no vertex left.

The DFS traversal uses the queue data structure to keep track of the unvisited nodes.

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G
lastly to D. It employs the following rules.

 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

 Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.

 Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Step Traversal Description

1 Initialize the queue.

We start from visiting S (starting

2
node), and mark it as visited.

We then see an unvisited adjacent

node from S. In this example, we
3 have three nodes but alphabetically
we choose A, mark it as visited and
enqueue it.

Next, the unvisited adjacent node

4 from S is B. We mark it as visited and
enqueue it.
 Next, the unvisited adjacent node
5 from S is C. We mark it as visited and
enqueue it.

Now, S is left with no unvisited

6 adjacent nodes. So, we dequeue and
find A.

From A we have D as unvisited

7 adjacent node. We mark it as visited
and enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on de
queuing in order to get all unvisited nodes. When the queue gets emptied, the program is over.

Spanning Tree
A spanning tree can be defined as the subgraph of an undirected connected graph. It includes all the
vertices along with the least possible number of edges. If any vertex is missed, it is not a spanning
tree. A spanning tree is a subset of the graph that does not have cycles, and it also cannot be
disconnected.

A spanning tree consists of (n-1) edges, where 'n' is the number of vertices (or nodes). Edges of the
spanning tree may or may not have weights assigned to them. All the possible spanning trees created
from the given graph G would have the same number of vertices, but the number of edges in the
spanning tree would be equal to the number of vertices in the given graph minus 1.

A complete undirected graph can have nn-2 number of spanning trees where n is the number of
vertices in the graph. Suppose, if n = 5, the number of maximum possible spanning trees would be 55-
2 = 125.

Applications of the spanning tree

Basically, a spanning tree is used to find a minimum path to connect all nodes of the graph. Some of
the common applications of the spanning tree are listed as follows -

o Cluster Analysis

o Civil network planning

o Computer network routing protocol

Now, let's understand the spanning tree with the help of an example.

Suppose the graph be -

As discussed above, a spanning tree contains the same number of vertices as the graph, the number
of vertices in the above graph is 5; therefore, the spanning tree will contain 5 vertices. The edges in
the spanning tree will be equal to the number of vertices in the graph minus 1. So, there will be 4
edges in the spanning tree.

Some of the possible spanning trees that will be created from the above graph are given as follows -
Properties of spanning-tree
Some of the properties of the spanning tree are given as follows -

o There can be more than one spanning tree of a connected graph G.

o A spanning tree does not have any cycles or loop.

o A spanning tree is minimally connected, so removing one edge from the tree will make the
graph disconnected.

o A spanning tree is maximally acyclic, so adding one edge to the tree will create a loop.

o There can be a maximum nn-2 number of spanning trees that can be created from a complete
graph.

o A spanning tree has n-1 edges, where 'n' is the number of nodes.

o If the graph is a complete graph, then the spanning tree can be constructed by removing
maximum (e-n+1) edges, where 'e' is the number of edges and 'n' is the number of vertices.

So, a spanning tree is a subset of connected graph G, and there is no spanning tree of a disconnected
graph.

Minimum Spanning tree

A minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the
edge is minimum. The weight of the spanning tree is the sum of the weights given to the edges of the
spanning tree. In the real world, this weight can be considered as the distance, traffic load,
congestion, or any random value.

Example of minimum spanning tree

The sum of the edges of the above graph is 16. Now, some of the possible spanning trees created
from the above graph are -

So, the minimum spanning tree that is selected from the above spanning trees for the given weighted
graph is -

Algorithms for Minimum spanning tree

A minimum spanning tree can be found from a weighted graph by using the algorithms given below -

o Prim's Algorithm

o Kruskal's Algorithm
Prim's Algorithm
Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph.
Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum
of the weights of the edges can be minimized.

Prim's algorithm starts with the single node and explores all the adjacent nodes with all the
connecting edges at every step. The edges with the minimal weights causing no cycles in the graph
got selected.

How does the prim's algorithm work?

Prim's algorithm is a greedy algorithm that starts from one vertex and continue to add the edges with
the smallest weight until the goal is reached. The steps to implement the prim's algorithm are given
as follows -

o First, we have to initialize an MST with the randomly chosen vertex.

o Now, we have to find all the edges that connect the tree in the above step with the new
vertices. From the edges found, select the minimum edge and add it to the tree.

o Repeat step 2 until the minimum spanning tree is formed.

The applications of prim's algorithm are -

o Prim's algorithm can be used in network designing.

o It can be used to make network cycles.

o It can also be used to lay down electrical wiring cables.

Example of prim's algorithm

Now, let's see the working of prim's algorithm using an example. It will be easier to understand the
prim's algorithm using an example.

Suppose, a weighted graph is -

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.

Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two edges from
vertex B that are B to C with weight 10 and edge B to D with weight 4. Among the edges, the edge BD
has the minimum weight. So, add it to the MST.

Step 3 - Now, again, choose the edge with the minimum weight among all the other edges. In this
case, the edges DE and CD are such edges. Add them to MST and explore the adjacent of C, i.e., E and
A. So, select the edge DE and add it to the MST.

Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would create a cycle to
the graph. So, choose the edge CA and add it to the MST.
So, the graph produced in step 5 is the minimum spanning tree of the given graph. The cost of the
MST is given below -

Cost of MST = 4 + 2 + 1 + 3 = 10 units.

Algorithm
1. Step 1: Select a starting vertex

2. Step 2: Repeat Steps 3 and 4 until there are fringe vertices

3. Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weig
ht

4. Step 4: Add the selected edge and the vertex to the minimum spanning tree T

5. [END OF LOOP]

6. Step 5: EXIT

Kruskal's Algorithm
Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The
main target of the algorithm is to find the subset of edges by using which we can traverse every
vertex of the graph. It follows the greedy approach that finds an optimum solution at every stage
instead of focusing on a global optimum.

How does Kruskal's algorithm work?

In Kruskal's algorithm, we start from edges with the lowest weight and keep adding the edges until
the goal is reached. The steps to implement Kruskal's algorithm are listed as follows -

o First, sort all the edges from low weight to high.

o Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be
added creates a cycle, then reject the edge.

o Continue to add the edges until we reach all vertices, and a minimum spanning tree is created.

The applications of Kruskal's algorithm are -

o Kruskal's algorithm can be used to layout electrical wiring among cities.

 o It can be used to lay down LAN connections.

Example of Kruskal's algorithm

Now, let's see the working of Kruskal's algorithm using an example. It will be easier to understand
Kruskal's algorithm using an example.

Suppose a weighted graph is -

The weight of the edges of the above graph is given in the below table -

Edge AB AC AD AE BC CD DE

Weight 1 7 10 5 3 4 2

Now, sort the edges given above in the ascending order of their weights.

Edge AB DE BC CD AE AC AD

Weight 1 2 3 4 5 7 10

Now, let's start constructing the minimum spanning tree.

Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle.
Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the cycle, so discard
it.

Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it.

Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so discard it.

So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal's
algorithm is -
The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Now, the number of edges in the above tree equals the number of vertices minus 1. So, the algorithm
stops here.

Algorithm
1. Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree.

2. Step 2: Create a set E that contains all the edges of the graph.

3. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning

4. Step 4: Remove an edge from E with minimum weight

5. Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F
(for combining two trees into one tree).

6. ELSE

7. Discard the edge

8. Step 6: END

Transitive closure of a Graph

Transitive Closure it the reachability matrix to reach from vertex u to vertex v of a graph. One graph is
given, we have to find a vertex v which is reachable from another vertex u, for all vertex pairs (u, v).
The final matrix is the Boolean type. When there is a value 1 for vertex u to vertex v, it means that
there is at least one path from u to v.

Dijkstra's Algorithm

Dijkstra algorithm is a single-source shortest path algorithm. Here, single-source means that only one
source is given, and we have to find the shortest path from the source to all the nodes.

Let's understand the working of Dijkstra's algorithm. Consider the below graph.

First, we have to consider any vertex as a source vertex. Suppose we consider vertex 0 as a source
vertex.

Here we assume that 0 as a source vertex, and distance to all the other vertices is infinity. Initially, we
do not know the distances. First, we will find out the vertices which are directly connected to the
vertex 0. As we can observe in the above graph that two vertices are directly connected to vertex 0.

Let's assume that the vertex 0 is represented by 'x' and the vertex 1 is represented by 'y'. The
distance between the vertices can be calculated by using the below formula:

1. d(x, y) = d(x) + c(x, y) < d(y)

 2. = (0 + 4) < ∞

3. = 4 < ∞

Since 4<∞ so we will update d(v) from ∞ to 4.

Therefore, we come to the conclusion that the formula for calculating the distance between the
vertices:

1. {if( d(u) + c(u, v) < d(v))

2. d(v) = d(u) +c(u, v) }

Now we consider vertex 0 same as 'x' and vertex 4 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (0 + 8) < ∞

3. = 8 < ∞

Therefore, the value of d(y) is 8. We replace the infinity value of vertices 1 and 4 with the values 4
and 8 respectively. Now, we have found the shortest path from the vertex 0 to 1 and 0 to 4.
Therefore, vertex 0 is selected. Now, we will compare all the vertices except the vertex 0. Since vertex
1 has the lowest value, i.e., 4; therefore, vertex 1 is selected.

Since vertex 1 is selected, so we consider the path from 1 to 2, and 1 to 4. We will not consider the
path from 1 to 0 as the vertex 0 is already selected.

First, we calculate the distance between the vertex 1 and 2. Consider the vertex 1 as 'x', and the
vertex 2 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (4 + 8) < ∞

3. = 12 < ∞

Since 12<∞ so we will update d(2) from ∞ to 12.

Now, we calculate the distance between the vertex 1 and vertex 4. Consider the vertex 1 as 'x' and
the vertex 4 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (4 + 11) < 8

3. = 15 < 8

Since 15 is not less than 8, we will not update the value d(4) from 8 to 12.
Till now, two nodes have been selected, i.e., 0 and 1. Now we have to compare the nodes except the
node 0 and 1. The node 4 has the minimum distance, i.e., 8. Therefore, vertex 4 is selected.

Since vertex 4 is selected, so we will consider all the direct paths from the vertex 4. The direct paths
from vertex 4 are 4 to 0, 4 to 1, 4 to 8, and 4 to 5. Since the vertices 0 and 1 have already been
selected so we will not consider the vertices 0 and 1. We will consider only two vertices, i.e., 8 and 5.

First, we consider the vertex 8. First, we calculate the distance between the vertex 4 and 8. Consider
the vertex 4 as 'x', and the vertex 8 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (8 + 7) < ∞

3. = 15 < ∞

Since 15 is less than the infinity so we update d(8) from infinity to 15.

Now, we consider the vertex 5. First, we calculate the distance between the vertex 4 and 5. Consider
the vertex 4 as 'x', and the vertex 5 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (8 + 1) < ∞

3. = 9 < ∞

Since 5 is less than the infinity, we update d(5) from infinity to 9.

Till now, three nodes have been selected, i.e., 0, 1, and 4. Now we have to compare the nodes except
the nodes 0, 1 and 4. The node 5 has the minimum value, i.e., 9. Therefore, vertex 5 is selected.

Since the vertex 5 is selected, so we will consider all the direct paths from vertex 5. The direct paths
from vertex 5 are 5 to 8, and 5 to 6.

First, we consider the vertex 8. First, we calculate the distance between the vertex 5 and 8. Consider
the vertex 5 as 'x', and the vertex 8 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (9 + 15) < 15

3. = 24 < 15

Since 24 is not less than 15 so we will not update the value d(8) from 15 to 24.

Now, we consider the vertex 6. First, we calculate the distance between the vertex 5 and 6. Consider
the vertex 5 as 'x', and the vertex 6 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (9 + 2) < ∞</p>
 3. = 11 < ∞

Since 11 is less than infinity, we update d(6) from infinity to 11.

Till now, nodes 0, 1, 4 and 5 have been selected. We will compare the nodes except the selected
nodes. The node 6 has the lowest value as compared to other nodes. Therefore, vertex 6 is selected.

Since vertex 6 is selected, we consider all the direct paths from vertex 6. The direct paths from vertex
6 are 6 to 2, 6 to 3, and 6 to 7.

First, we consider the vertex 2. Consider the vertex 6 as 'x', and the vertex 2 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (11 + 4) < 12

3. = 15 < 12

Since 15 is not less than 12, we will not update d(2) from 12 to 15

Now we consider the vertex 3. Consider the vertex 6 as 'x', and the vertex 3 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (11 + 14) < ∞

3. = 25 < ∞

Since 25 is less than ∞, so we will update d(3) from ∞ to 25.

Now we consider the vertex 7. Consider the vertex 6 as 'x', and the vertex 7 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (11 + 10) < ∞

3. = 22 < ∞

Since 22 is less than ∞ so, we will update d(7) from ∞ to 22.

Till now, nodes 0, 1, 4, 5, and 6 have been selected. Now we have to compare all the unvisited nodes,
i.e., 2, 3, 7, and 8. Since node 2 has the minimum value, i.e., 12 among all the other unvisited nodes.
Therefore, node 2 is selected.

Since node 2 is selected, so we consider all the direct paths from node 2. The direct paths from node
2 are 2 to 8, 2 to 6, and 2 to 3.

First, we consider the vertex 8. Consider the vertex 2 as 'x' and 8 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (12 + 2) < 15
 3. = 14 < 15

Since 14 is less than 15, we will update d(8) from 15 to 14.

Now, we consider the vertex 6. Consider the vertex 2 as 'x' and 6 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (12 + 4) < 11

3. = 16 < 11

Since 16 is not less than 11 so we will not update d(6) from 11 to 16.

Now, we consider the vertex 3. Consider the vertex 2 as 'x' and 3 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (12 + 7) < 25

3. = 19 < 25

Since 19 is less than 25, we will update d(3) from 25 to 19.

Till now, nodes 0, 1, 2, 4, 5, and 6 have been selected. We compare all the unvisited nodes, i.e., 3, 7,
and 8. Among nodes 3, 7, and 8, node 8 has the minimum value. The nodes which are directly
connected to node 8 are 2, 4, and 5. Since all the directly connected nodes are selected so we will not
consider any node for the updation.

The unvisited nodes are 3 and 7. Among the nodes 3 and 7, node 3 has the minimum value, i.e., 19.
Therefore, the node 3 is selected. The nodes which are directly connected to the node 3 are 2, 6, and
7. Since the nodes 2 and 6 have been selected so we will consider these two nodes.

Now, we consider the vertex 7. Consider the vertex 3 as 'x' and 7 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (19 + 9) < 21

3. = 28 < 21

Since 28 is not less than 21, so we will not update d(7) from 28 to 21.

Let's consider the directed graph.

Here, we consider A as a source vertex. A vertex is a source vertex so entry is filled with 0 while other
vertices filled with ∞. The distance from source vertex to source vertex is 0, and the distance from
the source vertex to other vertices is ∞.

We will solve this problem using the below table:

A B C D E

∞ ∞ ∞ ∞ ∞

Since 0 is the minimum value in the above table, so we select vertex A and added in the second row
shown as below:

A B C D E

A 0 ∞ ∞ ∞ ∞

As we can observe in the above graph that there are two vertices directly connected to the vertex A,
i.e., B and C. The vertex A is not directly connected to the vertex E, i.e., the edge is from E to A. Here
we can calculate the two distances, i.e., from A to B and A to C. The same formula will be used as in
the previous problem.

1. If(d(x) + c(x, y) < d(y))

2. Then we update d(y) = d(x) + c(x, y)

A B C D E

A 0 ∞ ∞ ∞ ∞
 10 5 ∞ ∞

As we can observe in the third row that 5 is the lowest value so vertex C will be added in the third
row.

We have calculated the distance of vertices B and C from A. Now we will compare the vertices to find
the vertex with the lowest value. Since the vertex C has the minimum value, i.e., 5 so vertex C will be
selected.

Since the vertex C is selected, so we consider all the direct paths from the vertex C. The direct paths
from the vertex C are C to B, C to D, and C to E.

First, we consider the vertex B. We calculate the distance from C to B. Consider vertex C as 'x' and
vertex B as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (5 + 3) < ∞

3. = 8 < ∞

Since 8 is less than the infinity so we update d(B) from ∞ to 8. Now the new row will be inserted in
which value 8 will be added under the B column.

A B C D E

A 0 ∞ ∞ ∞ ∞

10 5 ∞ ∞

We consider the vertex D. We calculate the distance from C to D. Consider vertex C as 'x' and vertex D
as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (5 + 9) < ∞

3. = 14 < ∞

Since 14 is less than the infinity so we update d(D) from ∞ to 14. The value 14 will be added under
the D column.

A B C D E
 A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

8 14

We consider the vertex E. We calculate the distance from C to E. Consider vertex C as 'x' and vertex E
as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (5 + 2) < ∞

3. = 7 < ∞

Since 14 is less than the infinity so we update d(D) from ∞ to 14. The value 14 will be added under
the D column.

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

8 14 7

As we can observe in the above table that 7 is the minimum value among 8, 14, and 7. Therefore, the
vertex E is added on the left as shown in the below table:

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

E 8 14 7

The vertex E is selected so we consider all the direct paths from the vertex E. The direct paths from
the vertex E are E to A and E to D. Since the vertex A is selected, so we will not consider the path from
E to A.
Consider the path from E to D.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (7 + 6) < 14

3. = 13 < 14

Since 13 is less than the infinity so we update d(D) from ∞ to 13. The value 13 will be added under
the D column.

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

E 8 14 7

B 8 13

The value 8 is minimum among 8 and 13. Therefore, vertex B is selected. The direct path from B is B
to D.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (8 + 1) < 13

3. = 9 < 13

Since 9 is less than 13 so we update d(D) from 13 to 9. The value 9 will be added under the D column.

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

E 8 14 7

B 8 13
 D 9

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.

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

Let the given graph be:

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

1. 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

2. 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
through 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.

3. 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.

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 .

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

6. Similarly, A3 and A4 is also created.

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

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

9. A4 gives the shortest path between each pair of vertices.