Graph, Spanning Tree & Shortest Path Algorithm Unit-4

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).
So, a graph is a non-linear data structure in programming that consists of finite sets of
nodes or vertices and a set of edges that connect these vertices to them.

Components of a Graph

 Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are
also known as vertex or nodes. Every node/vertex can be labelled or unlabelled.

 Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered
pair of nodes in a directed graph. Edges can connect any two nodes in any possible
way. There are no rules. Sometimes, edges are also known as arcs. Every edge can
be labelled/unlabelled.

Directed Graph: A directed graph is graph that consists of a set of objects (called
vertices or nodes) that are connected together, where all the edges are directed from
one vertex to another. A directed graph is sometimes called a digraph or a
directed network.
In a graph, the directed edge or arrow points from the first/ original vertex to the second/
destination vertex in the pair. In the N-vertex graph, we will represent vertices by the
name 1 through N.

On the basis of the aforementioned definition of a directed graph, a digraph is allowed to

have loops. That means they can contain the arrows which directly connects nodes to
themselves. If the directed graph has loops, that graph will be known as the loop digraph.
In the following directed graph, there are only directed edges. It contains a directed edge
from one vertex to any other vertex and a loop.
Algorithm P a g e 1 | 30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

A narrower definition is allowed by some authors, which says that the digraph is not
allowed to contain the loops. More specifically, if the digraph does not have the loops, that
graph will be known as the simple directed graph. In the following directed graph, there
are only directed edges. It contains a directed edge from one vertex to any other vertex,
and it is not allowing looping.

Undirected Graph: The undirected graph is also referred to as the bidirectional. It is a set
of objects (also called vertices or nodes), which are connected together. Here the edges
will be bidirectional. The two nodes are connected with a line, and this line is known as
an edge. The undirected graph will be represented as G = (N, E). Where N is used to show
the set of edges and E is used to show the set of edges, which are unordered pairs of
elements N. The main difference between the directed and undirected graph is that the
directed graph uses the arrow or directed edge to connect the two nodes. The arrow
points from the original vertex to destination vertex in the directed graph. While in the
undirected graph, the two nodes are connected with the two direction edges.

Example:

In this example, we will assume a graph where G = {N, E}. Where N = {1, 2, 3, 4}, and E =
{(1, 2), (1, 4), (3, 4), (2, 3)}. Now we have to draw a graph for these vertices and edges.

Algorithm P a g e 2 | 30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

There is another way to draw the undirected graph with the help of given vertices and
edges:

Some Terminologies related to the Graph:

Walk: A walk can be defined as a sequence of edges and vertices of a graph. When we have
a graph and traverse it, then that traverse will be known as a walk. In a walk, there can
be repeated edges and vertices. The number of edges which is covered in a walk will be
known as the Length of the walk. In a graph, there can be more than one walk.

So for a walk, the following two points are important, which are described as follows:

o Edges can be repeated

o Vertex can be repeated

For example: In this example, we have a graph, which is described as follows:

Algorithm P a g e 3 | 30
 Graph, Spanning Tree & Shortest Path Algorithm Unit-4

In the above graph, there can be many walks, but some of them are described as follows:

1. 1. A, B, C, E, D (Number of length = 4)
2. 2. D, B, A, C, E, D, C (Number of length = 7)
3. 3. E, C, B, A, C, E, D (Number of length = 6)

Types of Walks

There are two types of the walk, which are described as follows:

1. Open walk
2. Closed walk

Open Walk:

A walk will be known as an open walk in the graph theory if the vertices at which the walk
starts and ends are different. That means for an open walk, the starting vertex and ending
vertex must be different. In an open walk, the length of the walk must be more than 0.

Closed Walk:

A walk will be known as a closed walk in the graph theory if the vertices at which the walk
starts and ends are identical. That means for a closed walk, the starting vertex and ending
vertex must be the same. In a closed walk, the length of the walk must be more than 0.

o The walk will be known as the Trivial walk if length of the walk = 0.
o In case of the open walk and closed walk, the edges and vertices can be repeated.

Suppose there is a graph, which is described as follows:

Algorithm P a g e 4 | 30
 Graph, Spanning Tree & Shortest Path Algorithm Unit-4

In this graph, there is also a closed walk and an open walk, which are described as follows:

1. Closed walk = A, B, C, D, E, C, A
2. Open walk = A, B, C, D, E, C

Trails: A trail can be described as an open walk where no edge is allowed to repeat. In the
trails, the vertex can be repeated.

So for a trail, the following point is important, which is described as follows:

o Vertex can be repeated

In the above graph, there is a tail and closed tail, which is described as follows:

1. Tail = A, C, H, F, C, B
2. Closed tail = A, C, H, F, C, B, A

Circuit: A circuit can be described as a closed walk where no edge is allowed to repeat.
In the circuit, the vertex can be repeated. A closed trail in the graph theory is also known
as a circuit.

So for a circuit, the following two points are important, which are described as follows:

o Edges cannot be repeated

Algorithm P a g e 5 | 30
 Graph, Spanning Tree & Shortest Path Algorithm Unit-4

o Vertex can be repeated

In the above graph, there is a circuit, which is described as follows:

1. Circuit: A, B, D, C, F, H, C, A

Cycle: A closed path in the graph theory is also known as a Cycle. A cycle is a type of closed
walk where neither edges nor vertices are allowed to repeat. There is a possibility that
only the starting vertex and ending vertex are the same in a cycle.

So for a cycle, the following two points are important, which are described as follows:

o Edges cannot be repeated

o Vertex cannot be repeated

In the above graph, there is a cycle, which is described as follows:

1. Cycle: A, B, D, C, A

Path: A path is a type of open walk where neither edges nor vertices are allowed to
repeat. There is a possibility that only the starting vertex and ending vertex are the same
in a path. In an open walk, the length of the walk must be more than 0.

Algorithm P a g e 6 | 30
 Graph, Spanning Tree & Shortest Path Algorithm Unit-4

So for a path, the following two points are important, which are described as follows:

o Edges cannot be repeated

o Vertex cannot be repeated

In the above graph, there is a path, which is described as follows:

1. Path: F, H, C, A, B, D

Note:
o In discrete mathematics, every path can be a trail, but it is not possible that every
trail is a path.
o In discrete mathematics, every cycle can be a circuit, but it is not important that
every circuit is a cycle.
o If there is a directed graph, we have to add the term "directed" in front of all the
definitions defined above.
o In both the walks and paths, all sorts of graphical theoretical concepts are
considered. For example, suppose we have a graph and want to determine the
distance between two vertices. In this case, it will be considered the shortest path,
which begins at one and ends at the other. Here the length of the path will be equal
to the number of edges in the graph.

Important Chart:

The above definitions can be easily remembered with the help of following chart:

Algorithm P a g e 7 | 30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Directed Acyclic Graph:

In computer science and mathematics, a directed acyclic graph (DAG) refers to a directed
graph which has no directed cycles.
 Directed acyclic graphs are a type of data structure and they are used to apply
transformations to basic blocks.
 The Directed Acyclic Graph (DAG) facilitates the transformation of basic blocks.
 DAG is an efficient method for identifying common sub-expressions.
 It demonstrates how the statement’s computed value is used in subsequent
statements.

Directed Acyclic Graph Characteristics:

A Directed Acyclic Graph for Basic Block is a directed acyclic graph with the following
labels on nodes.
 The graph’s leaves each have a unique identifier, which can be variable names or
constants.
 The interior nodes of the graph are labelled with an operator symbol.
 In addition, nodes are given a string of identifiers to use as labels for storing the
computed value.
 Directed Acyclic Graphs have their own definitions for transitive closure and
transitive reduction.
 Directed Acyclic Graphs have topological orderings defined.

Explanation

In graph theory, a graph refers to a set of vertices which are connected by lines called
edges. In a directed graph or a digraph, each edge is associated with a direction from a
Algorithm P a g e 8 | 30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

start vertex to an end vertex. If we traverse along the direction of the edges and we find
that no closed loops are formed along any path, we say that there are no directed cycles.
The graph formed is a directed acyclic graph.
A DAG is always topologically ordered, i.e. for each edge in the graph, the start vertex of
the edge occurs earlier in the sequence than the ending vertex of the edge.

Example

In the above directed graph, if we find the paths from any node, say u, we will never find
a path that come back to u. Hence, this is a DAG.

Spanning Tree: A spanning tree is a subset of Graph G, which has all the vertices covered
with minimum possible number of edges. Hence, a spanning tree does not have cycles and
it cannot be disconnected.
By this definition, we can draw a conclusion that every connected and undirected Graph
G has at least one spanning tree. A disconnected graph does not have any spanning tree,
as it cannot be spanned to all its vertices.

Algorithm P a g e 9 | 30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

We found three spanning trees off one complete graph. A complete undirected graph can
have maximum nn-2 number of spanning trees, where n is the number of nodes. In the
above addressed example, n is 3, hence 33−2 = 3 spanning trees are possible.

General Properties of Spanning Tree:

We now understand that one graph can have more than one spanning tree. Following are
a few properties of the spanning tree connected to graph G −
 A connected graph G can have more than one spanning tree.
 All possible spanning trees of graph G, have the same number of edges and vertices.
 The spanning tree does not have any cycle (loops).
 Removing one edge from the spanning tree will make the graph disconnected, i.e.
the spanning tree is minimally connected.
 Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning
tree is maximally acyclic.

Mathematical Properties of Spanning Tree:

 Spanning tree has n-1 edges, where n is the number of nodes (vertices).
 From a complete graph, by removing maximum e - n + 1 edges, we can construct a
spanning tree.
 A complete graph can have maximum nn-2 number of spanning trees.

Prim’s Algorithm to determine Minimal Spanning Tree (MST):

Prim's algorithm to find minimum cost spanning tree (as Kruskal's algorithm) uses the
greedy approach. Prim's algorithm shares a similarity with the shortest path
first algorithms.
Prim's algorithm, in contrast with Kruskal's algorithm, treats the nodes as a single tree
and keeps on adding new nodes to the spanning tree from the given graph.

Step 1 - Remove all loops and parallel edges

Algorithm P a g e 10 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Remove all loops and parallel edges from the given graph. In case of parallel edges, keep
the one which has the least cost associated and remove all others.

Step 2 - Choose any arbitrary node as root node

In this case, we choose S node as the root node of Prim's spanning tree. This node is
arbitrarily chosen, so any node can be the root node. One may wonder why any video can
be a root node. So the answer is, in the spanning tree all the nodes of a graph are included
and because it is connected then there must be at least one edge, which will join it to the
rest of the tree.

Step 3 - Check outgoing edges and select the one with less cost

After choosing the root node S, we see that S,A and S,C are two edges with weight 7 and
8, respectively. We choose the edge S, A as it is lesser than the other.

Algorithm P a g e 11 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Now, the tree S-7-A is treated as one node and we check for all edges going out from it.
We select the one which has the lowest cost and include it in the tree.

After this step, S-7-A-3-C tree is formed. Now we'll again treat it as a node and will check
all the edges again. However, we will choose only the least cost edge. In this case, C-3-D
is the new edge, which is less than other edges' cost 8, 6, 4, etc.

After adding node D to the spanning tree, we now have two edges going out of it having
the same cost, i.e. D-2-T and D-2-B. Thus, we can add either one. But the next step will
again yield edge 2 as the least cost. Hence, we are showing a spanning tree with both
edges included.

Algorithm P a g e 12 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

We may find that the output spanning tree of the same graph using two different
algorithms is same.
Hence, the total Minimum Cost of the given Spanning Tree is 17.

Kruskal’s Algorithm to determine Minimal Spanning Tree (MST):

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach.
This algorithm treats the graph as a forest and every node it has as an individual tree. A
tree connects to another only and only if, it has the least cost among all available options
and does not violate MST properties.
To understand Kruskal's algorithm let us consider the following example:

Step 1 - Remove all loops and Parallel Edges

Remove all loops and parallel edges from the given graph.

Algorithm P a g e 13 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

In case of parallel edges, keep the one which has the least cost associated and remove all
others.

Step 2 - Arrange all edges in their increasing order of weight

The next step is to create a set of edges and weight, and arrange them in an ascending
order of weightage (cost).

Step 3 - Add the edge which has the least weightage

Now we start adding edges to the graph beginning from the one which has the least
weight. Throughout, we shall keep checking that the spanning properties remain intact.
In case, by adding one edge, the spanning tree property does not hold then we shall
consider not to include the edge in the graph.

Algorithm P a g e 14 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

The least cost is 2 and edges involved are B, D and D, T. We add them. Adding them does
not violate spanning tree properties, so we continue to our next edge selection.
Next cost is 3, and associated edges are A, C and C, D. We add them again –

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph.
−

We ignore it. In the process we shall ignore/avoid all edges that create a circuit.

Algorithm P a g e 15 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move
on.

Now we are left with only one node to be added. Between the two least cost edges
available 7 and 8, we shall add the edge with cost 7.

By adding edge S, A We have included all the nodes of the graph and we now have
minimum cost spanning tree.
Hence, the total Minimum Cost of the given Spanning Tree is 17.

Dijkstra Algorithm to determine the Shortest Path:

The Dijkstra’s algorithm finds the shortest path from a particular node, called the source
node to every other node in a connected graph. It produces a shortest path tree with the

Algorithm P a g e 16 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

source node as the root. It is profoundly used in computer networks to generate optimal
routes with the aim of minimizing routing costs.

Dijkstra’s Algorithm:

Input − A graph representing the network; and a source node, s

Output − A shortest path tree, spt[], with s as the root node.

Initializations −

 An array of distances dist[] of size |V| (number of nodes),

where dist[s] = 0 and dist[u] = ∞ (infinite), where u represents a node in the
graph except s.
 An array, Q, containing all nodes in the graph. When the algorithm runs into
completion, Q will become empty.
 An empty set, S, to which the visited nodes will be added. When the algorithm runs
into completion, S will contain all the nodes in the graph.
 Repeat while Q is not empty −
o Remove from Q, the node, u having the smallest dist[u] and which is not in
S. In the first run, dist[s] is removed.
o Add u to S, marking u as visited.
o For each node v which is adjacent to u, update dist[v] as −
 If (dist[u] + weight of edge u-v) < dist[v], Then
 Update dist[v] = dist[u] + weight of edge u-v
 The array dist[] contains the shortest path from s to every other node.

Example

The working of the algorithm can be best understood using an example. Consider the
following graph having nodes marked from A to G, connected by weighted edges as
follows

Algorithm P a g e 17 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

The initializations will be as follows

 dist[7]={0,∞,∞,∞,∞,∞,∞}
 Q={A,B,C,D,E,F,G}
 S𝑆= ∅
Pass 1 − We choose node A from Q since it has the lowest dist[] value of 0 and put it in
S. The neighbouring nodes of A are B and C. We update dist[] values corresponding to B
and C according to the algorithm. So the values of the data structures become
 dist[7]={0,5,6,∞,∞,∞,∞}
 Q={B,C,D,E,F,G}
 S={A}

The distances and shortest paths after this pass are shown in the following graph. The
green node denotes the node already added to S

Pass 2 − We choose node B from Q since it has the lowest dist[] value of 5 and put it
in S. The neighbouring nodes of B will be C, D and E. We update dist[] values
corresponding to C, D and E according to the algorithm. So the values of the data
structures become
 dist[7]={0,5,6,12,13,∞,∞}
 Q={C,D,E,F,G}
 S={A,B}

The distances and shortest paths after this pass are

Algorithm P a g e 18 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Pass 3 − We choose node C from Q since it has the lowest dist[] value of 6 and put it in S.
The neighbouring nodes of C will be D and F. We update dist[] values corresponding to
D and F. So the values of the data structures become
 dist[7]={0,5,6,8,13,10,∞}
 Q={D,E,F,G}
 S={A,B,C}

The distances and shortest paths after this pass are

Pass 4 − We choose node D from Q since it has the lowest dist[] value of 8 and put it in
S. The neighbouring nodes of D will be E, F and G. We update dist[] values corresponding
to E, F and G. So the values of the data structures become
 dist[7]={0,5,6,8,10,10,18}
Algorithm P a g e 19 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

 Q={E,F,G}
 S={A,B,C,D}

The distances and shortest paths after this pass are

Pass 5 − We can choose either node E or node F from Q since both of them have the
lowest dist[] value of 10. We select any one of them, say E, and put it in S. The
neighbouring nodes of D is G. We update dist[] values corresponding to G. So the values
of the data structures become
 dist[7]={0,5,6,8,10,10,13}
 Q={F,G}
 S={A,B,C,D,E}

The distances and shortest paths after this pass are

Algorithm P a g e 20 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Pass 6 − We choose node F from Q since it has the lowest dist[] value of 10 and put it
in S. The neighbouring nodes of F is G. The dist[] value corresponding to G is less than
that through F. So it remains same. The values of the data structures become
 dist[7]={0,5,6,8,10,10,13}
 Q={G}
 S={A,B,C,D,E,F}

The distances and shortest paths after this pass are

Pass 7 − There is just one node in Q. We remove it from Q put it in S. The dist[] array
needs no change. Now, Q becomes empty, S contains all the nodes and so we come to the
end of the algorithm. We eliminate all the edges or routes that are not in the path of any
route. So the shortest path tree from source node A to all other nodes are as follows

Algorithm P a g e 21 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Bellman Ford Algorithm: Bellman ford is a single source shortest path algorithm based on the
bottom-up approach of dynamic programming. It starts from a single vertex and calculates the
shortest path from the starting vertex to all the nodes in a weighted graph.

In data structures, there are various other algorithms for the shortest path like the Dijkstra
algorithm, Kruskal’s algorithm, Prim’s algorithm, etc. But all these algorithms work only when the
given edge weight is positive in a graph. No algorithm provides an accurate solution when there is
an edge with a negative weight.

So, Bellman Ford’s algorithm deals with graphs that have negative edge weights and guarantees to
calculate the correct and optimized shortest path between vertices.

Bellman-Ford algorithm is based on the “Principle of Relaxation”

Negative edge weights of the graph can generate a negative cycle in the graph and with Dijkstra
and another algorithm it is very difficult to find the shortest path when there is a negative edge in
the graph, so bellman ford algorithm resolves this problem.

Working Principle of Bellman Ford Algorithm:

Algorithm P a g e 22 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Now, let’s know the working of the bellman ford algorithm, and how exactly the algorithm deals
with negative edges using dynamic programming approaches. The step-by-step working of the
algorithm is as follows:

Step-1: Initialize the distance value Infinite to every other vertex and set distance value 0 to the
source node itself.

Step-2: Visit each edge and relax the path if the previous path was not accurate. To relax the path
for vertices and for edge u-v:

If, (d (u) + c (u, v) < d (v))

d (v) = d(u) + c(u , v)

The above equation means if the sum of distance value of source node and cost of moving from
source to destination is less than distance of source vertex. Then, the distance value of destination
vertex from the source vertex will be equals to distance value of the source and cost of reaching
the destination from source.

Step-3: If the new distance value is less than the previous one, then update the distance value in
each iteration for the edges. The distance value to every node is the total distance from the starting
vertex to that particular vertex.

Step-4: Repeat the above steps multiple iterations, to ensure the obtained result is optimized.

Example

Consider the following graph, and find the shortest path using the bellman ford algorithm.

Algorithm P a g e 23 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Solution:

Initially, the distance of each vertex will be infinity from the source vertex and source-to-source
distance value would be zero. So, considering A to be source vertex

Relax all the edges n-1 times, where n is the number of vertices

If, [(d (u) + c (u, v) < d (v))]

d (v) = d (u) + c (u, v)

So, for this problem, there will be total 5 iteration as (6-1).

List out all the edges in the graph.

(A, B), (A, C), (A, D), (B, E), (D, C), (D, F) (C, E), (C, B), (E, F)

First iteration:

Let’s take (A, B), here d (u) is 0, d (v) is ∞ and c (u, v) is 6.

Putting, these value in “Principle of relaxation”

If, [0 + 6 < ∞]…… True

So, [d (B) = 6]

Now, let’s take (A, C)

On putting “Principle of relaxation”

Algorithm P a g e 24 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

[d (C) = 4]

Now, let’s take (A, D)

On putting “Principle of relaxation”

[d (D) = 5 ]

Now, let’s take (B, E)

On putting “Principle of relaxation”

If, [6 + (-1) < ∞]…… True

So, [d (E) = 5]

Now, let’s take (C, E)

On putting “Principle of relaxation”

If, [4 + 3 < 5]…… False

So, don’t update.

Now, let’s take (D, C)

On putting “Principle of relaxation”

If, [5+ (-2) < 4]…… True

So, [d (C) = 3]

Now, let’s take (D, F)

On putting “Principle of relaxation”

If, [5+ (-1) < ∞]…… True

So, [d (F) = 4]

Now, let’s take (E, F)

On putting “Principle of relaxation”

If, [5+ 3 < 4]…… False

Algorithm P a g e 25 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

So, Don’t Update

Now, let’s take (C, B)

On putting “Principle of relaxation”

If, [3+ (-2) < 6]…… True

So, [d (B) = 1 ]

The graph after first iteration looks as follows:

Second Iteration:

Let’s take (A, B),

Putting, these value in “Principle of relaxation”

If, [0 + 6 < 1]…… False

So, don’t update

Now, let’s take (A, C)

On putting “Principle of relaxation”

If, [0 + 4 < 3]…… False

So, don’t update

Now, let’s take (A, D)

Algorithm P a g e 26 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

On putting “Principle of relaxation”

If, [0 + 5 < 5]…… False

So, don’t update

Now, let’s take (B, E)

On putting “Principle of relaxation”

If, [1 + (-1) < 5]…… True

So, [d (E) = 0 ]

Now, let’s take (C, E)

On putting “Principle of relaxation”

If, [3 + 3 < 0]…… False

So, don’t update.

Now, let’s take (D, C)

On putting “Principle of relaxation”

If, [5+ (-2) < 3]…… False

So, Don’t Update

Now, let’s take (D, F)

On putting “Principle of relaxation”

If, [5+ (-1) < 4]…… False

So, Don’t Update

Now, let’s take (E, F)

On putting “Principle of relaxation”

If, [0+ 3 < 4]…… True

So, [d (F) = 3]
Algorithm P a g e 27 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

Now, let’s take (C, B)

On putting “Principle of relaxation”

If, [3+ (-2) < 6]…… False

So, Don’t Update

The Graph after second iteration

Third Iteration:

Let’s take (A, B),

Putting, these values in the “Principle of relaxation”

If, [0 + 6 < 1]…… False

So, don’t update

Now, let’s take (A, C)

On putting “Principle of relaxation”

If, [0 + 4 < 3]…… False

So, don’t update

Now, let’s take (A, D)

On putting “Principle of relaxation”

If, [0 + 5 < 5]…… False

Algorithm P a g e 28 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

So, don’t update

Now, let’s take (B, E)

On putting “Principle of relaxation”

If, [1 + (-1) < 0……. False

So, don’t update

Now, let’s take (C, E)

On putting “Principle of relaxation”

If, [3 + 3 < 0]…… False

So, don’t update.

Now, let’s take (D, C)

On putting “Principle of relaxation”

If, [5+ (-2) < 3]…… False

So, Don’t Update

Now, let’s take (D, F)

On putting “Principle of relaxation”

If, [5+ (-1) < 3]…… False

So, Don’t Update

Now, let’s take (E, F)

On putting “Principle of relaxation”

If, [0+ 3 < 3]…… False

So, Don’t Update

Now, let’s take (C, B)

On putting “Principle of relaxation”

Algorithm P a g e 29 |
30
Graph, Spanning Tree & Shortest Path Algorithm Unit-4

If, [3+ (-2) < 6]…… False

So, Don’t Update

The graph after the third iteration is

According to the relaxation condition, we need at most five iterations, as we can see there are no
updating or changes in the third iteration itself. So, we will stop here and write the shortest path
of each vertex from A.

So, the cost for each vertex from A is

A- A: 0

A- B: 1

A- C: 3

A- D: 5

A- E: 0

A- F: 3

Algorithm P a g e 30 |
30