Graph

A graph can be defined as group of vertices and edges that are used to connect these vertices. A graph can be
seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of
having parent child relationship.
Definition
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G)
represents the set of edges which are used to connect these vertices.
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is
shown in the following figure.

Graph Terminology
Vertex
Individual data element of a graph is called as Vertex. Vertex is also known as node. In above example graph,
A, B, C, D & E are known as vertices.
Edge
An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(starting Vertex, ending Vertex). For example, in above graph the link between vertices A and B is represented
as (A,B). In above example graph, there are 7 edges (i.e., (A,B), (A,D), (B,D), (B,C), (B,D), (E,D), (C,E)).
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 V0=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 neighbors 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.
In degree
Total number of incoming edges connected to a vertex is said to be indegree of that vertex.
Out degree
Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges with same end vertices and two directed edges with same origin and
destination, such edges are called parallel edges or multiple edges.
Undirected Graph
A graph with only undirected edges is said to be undirected graph.
Directed Graph
A graph with only directed edges is said to be directed graph.
Mixed Graph
A graph with both undirected and directed edges is said to be mixed graph.

Articulation Points (or Cut Vertices) in a Graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges
through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single
points whose failure would split the network into 2 or more disconnected components. They are useful for
designing reliable networks.

Graph Representation
There are two ways to store Graph into the computer's memory.

1) Sequential Representation
a) Adjacency Matrix
b) Incidence Matrix
2) Linked Representation
a) Adjacency List

Sequential Representation
in sequential representation, we use adjacency matrix to store the mapping represented by vertices and edges. In
adjacency matrix, the rows and columns are represented by the graph vertices. A graph having n vertices, will
have a dimension n x n.
An entry Mij in the adjacency matrix representation of an undirected graph G will be 1 if there exists an edge
between Vi and Vj.An undirected graph and its adjacency matrix representation is shown in the following figure.

in the above figure, we can see the mapping among the vertices (A, B, C, D, E) is represented by using the
adjacency matrix which is also shown in the figure.

There exists different adjacency matrices for the directed and undirected graph. In directed graph, an entry
Aij will be 1 only when there is an edge directed from Vi to Vj.

A directed graph and its adjacency matrix representation is shown in the following figure.

Representation of weighted directed graph is different. Instead of filling the entry by 1, the Non- zero entries of
the adjacency matrix are represented by the weight of respective edges.

The weighted directed graph along with the adjacency matrix representation is shown in the following figure.
Linked Representation
In the linked representation, an adjacency list is used to store the Graph into the computer's memory.
Consider the undirected graph shown in the following figure and check the adjacency list representation.

An adjacency list is maintained for each node present in the graph which stores the node value and a pointer to
the next adjacent node to the respective node. If all the adjacent nodes are traversed then store the NULL in the
pointer field of last node of the list. The sum of the lengths of adjacency lists is equal to the twice of the number
of edges present in an undirected graph.
Consider the directed graph shown in the following figure and check the adjacency list representation of the
graph.

In a directed graph, the sum of lengths of all the adjacency lists is equal to the number of edges present in the
graph.
In the case of weighted directed graph, each node contains an extra field that is called the weight of the node.
The adjacency list representation of a directed graph is shown in the following figure.
Incidence Matrix
In this representation, the graph is represented using a matrix of size total number of vertices by a total number
of edges. That means graph with 4 vertices and 6 edges is represented using a matrix of size 4X6. In this matrix,
rows represent vertices and columns represents edges. This matrix is filled with 0 or 1 or -1. Here, 0 represents
that the row edge is not connected to column vertex, 1 represents that the row edge is connected as the outgoing
edge to column vertex and -1 represents that the row edge is connected as the incoming edge to column vertex.

For example, consider the following directed graph representation...

Time complexity Create Add Add edge Remove Remove Search

vertex vertex edge
Adjacency list O(|V|+|E|) O(1) O(1) O(|V|+|E|) O(|E|) O(|V|)
Incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
Adjacency matrix O(|V|2) O(|V|2) O(1) O(|V|2) O(1) O(1)
Incidence matrix O(|V|*|E|) O(|V|*|E|) O(|V|*|E|) O(|V|*|E|) O(|V|*|E|) O(|E|)
 Graph Traversal
Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is also used to decide
the order of vertices is visited in the search process. A graph traversal finds the edges to be used in the search
process without creating loops. That means using graph traversal we visit all the vertices of the graph without
getting into looping path.
There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)
2. BFS (Breadth First Search)
Depth First Search (DFS) Algorithm
Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes to deeper and
deeper until we find the goal node or the node which has no children. The algorithm, then backtracks from the
dead end towards the most recent node that is yet to be completely unexplored.
The data structure which is being used in DFS is stack. The process is similar to BFS algorithm. In DFS, the
edges that leads to an unvisited node are called discovery edges while the edges that leads to an already visited
node are called block edges.
Algorithm
o Step 1: SET STATUS = 1 (ready state) for each node in G
o Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
o Step 3: Repeat Steps 4 and 5 until STACK is empty
o Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
o Step 5: Push on the stack all the neighbours of N that are in the ready state (whose STATUS = 1) and
set their
STATUS = 2 (waiting state)
[END OF LOOP]
o Step 6: EXIT

DFS traversal is not unique.

The total running time for Depth First Search is O (V+E).

Complexity Analysis of Depth First Search

Time Complexity
 The time complexity of DFS if the entire tree is traversed is O(V) where V is the number of nodes.
 If the graph is represented as adjacency list:
o Here, each node maintains a list of all its adjacent edges. Let’s assume that there are V number of
nodes and E number of edges in the graph.
o For each node, we discover all its neighbors by traversing its adjacency list just once in linear
time.
o For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E. So, the time
complexity in this case is O(V) + O(E) = O(V + E).
o For an undirected graph, each edge appears twice. Once in the adjacency list of either end of the
edge. The time complexity for this case will be O(V) + O (2E) ~ O(V + E).
 If the graph is represented as an adjacency matrix (a V x V array):
o For each node, we will have to traverse an entire row of length V in the matrix to discover all its
outgoing edges.
 o Note that each row in an adjacency matrix corresponds to a node in the graph, and that row
stores information about edges emerging from the node. Hence, the time complexity of DFS in
this case is O(V * V) = O(V2).
 The time complexity of DFS actually depends on the data structure being used to represent the graph.
Space Complexity
 Since we are maintaining a stack to keep track of the last visited node, in worst case, the stack could take
upto the size of the nodes(or vertices) in the graph. Hence, the space complexity is O(V).

Example :
Consider the graph G along with its adjacency list, given in the figure below. Calculate the order to print all the
nodes of the graph starting from node H, by using depth first search (DFS) algorithm.

Solution :

Let us assume ,starting node is H

Step1.
Push H onto the stack and status of H become 2
STACK : H
Status 1: A B C D E F G Status 2 H Status 3
Step2.
POP the top element of the stack i.e. H, print it , status of H is now 3 and push all the neighbours of H onto the
stack that are is ready statei.e A. status of A is now 2
 Print H
 STACK : A
Status 1: B C D E F G Status 2 A Status 3 H
Step3.
Pop the top element of the stack i.e. A, print it, status of A is now 3 and push all the neighbours of A onto the
stack that are in ready state i.eB,D. the status of B&D are 2
 Print A
 Stack : B, D
Status 1: C E F G Status 2 B D Status 3 H A

Step 4:
Pop the top element of the stack i.e. D, print it ,status of D is now 3and push all the neighbours of D onto the
stack that are in ready statei.e F.status of F is now 2
 Print D
  Stack : B, F

Status 1: C E G Status 2 B F Status 3 H A D

Step5:
Pop the top element of the stack i.e. F, print it , status of F is now 3and push all the neighbours of F onto the
stack that are in ready state. The neighbor of F is A but status of A is 3. So we cannot access it.
 Print F
 Stack : B

Status 1: C E G Status 2 B Status 3 H A D F

Step6:
Pop the top of the stack i.e. B, print it, status of B is now 3and push all the neighbours. The neighbours of B is C
and F, the status of F is 3 so we can’t push in to stack. Where status of C is 1 so we push C in to stack and status
of C become 2
 Print B
 Stack : C

Status 1: E G Status 2 C Status 3 H A D F B

Step7:
Pop the top of the stack i.e. C print it, status of C is now 3and push all the neighbours.The neighbours of C is E,
G, H, the status of H is now 3 so we can’t push in to stack. Where status of E&G is 1 so we push E&G in to
stack and status of E&G become 2

 Print C
 Stack : E, G

Status 1: Status 2 E G Status 3 H A D F B C

Step8:
Pop the top of the stack i.e. G,print it, status of G is now 3 and push all its neighbours. The neighbours of G is
E, H, the status of H is 3 and E is 2 so we can’t push in to stack.

 Print G
 Stack : E

Status 1: Status 2 E Status 3 H A D F B C G

Step9:
Pop the top of the stack i.e. E and push all its neighbours.The neighbours of E is B,F, the status of B,F is 3 so
we can’t push in to stack.

 Print E
 Stack :

Status 1: Status 2 Status 3 H A D F B C G E


Hence, the stack now becomes empty and all the nodes of the graph have been traversed.
The printing sequence of the graph will be :
H→A→D→F→B→C→G→E

Breadth First Search (BFS) Algorithm

Breadth first search is a graph traversal algorithm that starts traversing the graph from root node and explores all
the neighbouring nodes. Then, it selects the nearest node and explore all the unexplored nodes. The algorithm
follows the same process for each of the nearest node until it finds the goal.
The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all of
its neighbours. In the next step, the neighbours of the nearest node of A are explored and process continues in
the further steps. The algorithm explores all neighbours of all the nodes and ensures that each node is visited
exactly once and no node is visited twice.

Algorithm

o Step 1: SET STATUS = 1 (ready state) for each node in G

o Step 2: Enqueue the starting node A and set its STATUS = 2(waiting state)
o Step 3: Repeat Steps 4 and 5 until QUEUE is empty
o Step 4: Dequeue a node N. Process it and set its STATUS = 3(processed state).
o Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and set
their STATUS = 2 (waiting state)
[END OF LOOP]
o Step 6: EXIT

BFS traversal is not unique.

The total running time for Breadth First Search is O (V+E).

Complexity Analysis of Breadth First Search

Time Complexity
 The time complexity of BFS if the entire tree is traversed is O(V) where V is
the number of nodes.
 If the graph is represented as adjacency list:
o Here, each node maintains a list of all its adjacent edges. Let’s assume
that there are V number of nodes and E number of edges in the graph.
o For each node, we discover all its neighbors by traversing its adjacency
list just once in linear time.
 o For a directed graph, the sum of the sizes of the adjacency lists of all the
nodes is E. So, the time complexity in this case is O(V) + O(E) = O(V + E).
o For an undirected graph, each edge appears twice. Once in the adjacency
list of either end of the edge. The time complexity for this case will
be O(V) + O (2E) ~ O(V + E).
 If the graph is represented as an adjacency matrix (a V x V array):
o For each node, we will have to traverse an entire row of length V in the
matrix to discover all its outgoing edges.
o Note that each row in an adjacency matrix corresponds to a node in the
graph, and that row stores information about edges emerging from the
node. Hence, the time complexity of BFS in this case is O(V * V) = O(V2).
 The time complexity of BFS actually depends on the data structure being used to
represent the graph.

Space Complexity
 Since we are maintaining a priority queue (FIFO architecture) to keep track of
the visited nodes, in worst case, the queue could take upto the size of the
nodes(or vertices) in the graph. Hence, the space complexity is O(V).

Example :
Consider the graph G along with its adjacency list, given in the figure below. Calculate the order to print all the
nodes of the graph starting from node H, by using breadth first search (BFS) algorithm.

Solution:
Let us assume, starting node is H
Step1.
Insert H onto the queue and status of H become 2
QUEUE : H
Status 1: A B C D E F G Status 2 H Status 3
Step2.
Delete the element of the queue i.e. H, print it, status of H is now 3 and Insert all the neighbours of H onto the
queue that are is ready state i.e A. status of A is now 2
 Print H
 QUEUE: _, A
Status 1: B C D E F G Status 2 A Status 3 H
Step3.
Delete the element of the queue i.e. A, print it, status of A is now 3 and Insert all the neighbours of A onto the
queue that are in ready state i.e B,D. the status of B&D are 2
 Print A
 QUEUE : _, _,B, D
Status 1: C E F G Status 2 B D Status 3 H A

Step 4:
Delete the element of the queue i.e. B, print it , status of B is now 3and Insert all the neighbours of B onto the
queue that are in ready state i.e C &F. status of C&F is now 2
 Print B
 QUEUE : _,_,_,D, C ,F

Status 1: E G Status 2 D C F Status 3 H A B

Step5:
Delete the element of the queue i.e. D, print it , status of D is now 3and Insert all the neighbours of D onto the
queue that are in ready state. The neighbor of D is F but status of F is 2. So we cannot access it.
 Print D
 QUEUE : _,_,_,_, C ,F
Status 1: E G Status 2 C F Status 3 H A B D

Step6:
Delete the element of the queue i.e. C, print it, status of C is now 3and Insert all the neighbours. The neighbours
of C is E,G and H, the status of H is3 so we can’t Insert in to queue. Where status of E&G is 1 so we Insert
E&G in to queue and status of E&G become 2
 Print C
 QUEUE : _,_,_,_, _ ,F,E,G

Status 1: Status 2 F E G Status 3 H A B D C

Step7:
Delete the element of the queue i.e. F print it, status of F is now 3and Insert all the neighbours. The neighbours
of F is A. the status of A is 3 so we can’t Insert in to queue.
 Print F
 QUEUE : _,_,_,_, _ ,_,E, G

Status 1: Status 2 E G Status 3 H A B D C F

Step8:
Delete the element of the queue i.e. E, print it, status of E is now 3 and Insert all its neighbours. The neighbours
of E is B, F, the status of B&F is 3 so we can’t Insert in to queue.

 Print E
 QUEUE : _,_,_,_, _ ,_,_, G
Status 1: Status 2 G Status 3 H A B D C F E
Step9:
Delete the element of the queue i.e. G, print it and Insert all its neighbours. The neighbours of G is E&H, the
status of E&H is 3 so we can’t Insert in to queue.
 Print G
 QUEUE: _,_,_,_, _ ,_,_,_

Status 1: Status 2 Status 3 H A B D C F E G


Hence, the queue now becomes empty and all the nodes of the graph have been traversed.
The printing sequence of the graph will be :
H→A→B→D→C→F→E→G

Spanning Tree
Spanning tree can be defined as a sub-graph of connected, undirected graph G that is a tree produced by
removing the desired number of edges from a graph. In other words, Spanning tree is a non-cyclic sub-
graph of a connected and undirected graph G that connects all the vertices together. A graph G can have
multiple spanning trees.

Note1:Weight of a Graph: The sum of the weights of all edges

Note2:A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number
of nodes. In the example, n is 3, hence 33−2 = 3 spanning trees are possible.
Note3:Spanning tree has n-1 edges, where n is the number of nodes (vertices).
Note4:From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

Minimum Spanning Tree

There can be weights assigned to every edge in a weighted graph. However, A minimum spanning tree is
a spanning tree which has minimal total weight. In other words, minimum spanning tree is the one which
contains the least weight among all other spanning tree of some particular graph.

There are two algorithms which are being used for this purpose.
o Prim's Algorithm
o Kruskal's Algorithm

Prim's Algorithm
o Prim's Algorithm 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.
 o Prim's algorithm starts with the single node and explore 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.
o Prim’s Algorithm is a famous greedyalgorithm. (Greedy is an algorithmic paradigm that builds up a
solution piece by piece, always choosing the next piece that offers the most obvious and immediate
benefit. So the problems where choosing locally optimal also leads to global solution are best fit for
Greedy.)
Algorithm
Step-01:
 Randomly choose any vertex.
 The vertex connecting to the edge having least weight is usually selected.
Step-02:
 Find all the edges that connect the tree to new vertices.
 Find the least weight edge among those edges and include it in the existing tree.
 If including that edge creates a cycle, then reject that edge and look for the next least weight edge.
Step-03:
 Keep repeating step-02 until all the vertices are included and Minimum Spanning Tree (MST) is
obtained.

Problem-01:
Step-01: Step-02:

Step-03: Step-04:

Step-05: Step-06:

The above discussed steps are followed to find the minimum cost spanning tree using Prim’s Algorithm-
Since all the vertices have been included in the MST, so we stop.
Now, Cost of Minimum Spanning Tree
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
Problem-02:
Using Prim’s Algorithm, find the cost of minimum spanning tree (MST) of the given graph-
Solution-

The minimum spanning tree obtained by the application of Prim’s Algorithm on the given graph is as
shown below-

Now, Cost of Minimum Spanning Tree

= Sum of all edge weights
= 1 + 4 + 2 + 6 + 3 + 10
= 26 units

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.
Kruskal's algorithm follows greedy approach which finds an optimum solution at every stage instead of
focusing on a global optimum.
To apply Kruskal’s algorithm, the given graph must be weighted, connected and undirected.

Kruskal’s Algorithm
 Step-01:
Sort all the edges from low weight to high weight.
Step-02:
Take the edge with the lowest weight and use it to connect the vertices of graph.
If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.
Step-03:
Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.
Problem-01:
Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm-

Solution-
To construct MST using Kruskal’s Algorithm,
 Simply draw all the vertices on the paper.
 Connect these vertices using edges with minimum weights such that no cycle gets formed.
Step-01:

Step-02:
Step-03:

Step-04:
Step-05:

Step-06:

Step-07:

Since all the vertices have been connected / included in the MST, so we stop.
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units

Difference between Prim’s Algorithm and Kruskal’s Algorithm-

 Prim’s Algorithm Kruskal’s Algorithm

The tree that we are making or growing always The tree that we are making or growing usually remains
remains connected. disconnected.

Prim’s Algorithm grows a solution from a random Kruskal’s Algorithm grows a solution from the cheapest
vertex by adding the next cheapest vertex to the edge by adding the next cheapest edge to the existing
existing tree. tree / forest.

Prim’s Algorithm is faster for dense graphs.

Kruskal’s Algorithm is faster for sparse graphs.
(a dense graph is a graph in which the number of
(a graph with only a few edges, is a sparse graph)
edges is close to the maximal number of edges)

Time complexity O(V2). Kruskal’s time complexity is O(logV)

Note 1:If all the edge weights are distinct, then both the algorithms are guaranteed to find the same MST.
Example-
Consider the following example-

Here, both the algorithms on the above given graph produces the same MST as shown
Note 2:

 If all the edge weights are not distinct, then both the algorithms may not always produce the same MST.
 However, cost of both the MSTs would always be same in both the cases.

Example-

Consider the following example-

Here, both the algorithms on the above given graph produces different MSTs as shown but the cost is same in
both the cases.
 Shortest Path Problem-

 In general, Shortest path problem is a problem of finding the shortest path(s) between vertices or nodes in the
given graph.
 Shortest path between two vertices is a path that has the least cost as compared to all other paths that exists in
the graph.
 Dijkstra’s Algorithm is one of the very famous greedy algorithms.
Conditions for Dijkstra’s Algorithm-
1. Dijkstra’s algorithm works only for those graphs that are connected.
2. Dijkstra’s algorithm works only for those graphs that do not contain any edges with negative weights.
3. The actual Dijkstra’s algorithm does not output the shortest paths. It only provides the value or cost of the
shortest paths.
4. By making minor modifications in the actual algorithm, the shortest paths can be easily obtained.
5. Dijkstra’s algorithm works for directed as well as undirected graphs.

The Procedure is as –
1.Initially make source node permanent and make it the current working node.All other nodes are made
temporary
2.Examine all the temporary neighbours of the current working node and after checking the condition for
minimum weight , relabel the required nodes.
3.From all the temporary nodes,find out the node which has minimum value of dist , make this node permanent
and now this is our current working node.
4Repeat steps 2 and 3 until destination node is made permanent.

Relaxation of a node: the update the shortest path of a node is called Relaxation. Suppose u is the current
vertex and v is the neighbor vertex ,where c(u,v) is the cost of the path from u to v or this is weight of the path
from u to v. d(u) is distance from source to u. d(v) is the distance from source v.

Now if d(u)+c(u,v)<d(v) is true then we have to update the value of d(v) that is called relaxation
So if d(u)+c(u,v)<d(v) then new value of d(v)= d(u)+c(u,v) else the value of d(v) remain same.

u=a, v=b, d(u)=2,d(v)=8, c(u,v)=4. Now d(u)+c(u,v)<d(v) is true[2+4=6<8] so new value of d(v)=6
Working Example of Dijkstra's Algorithm
In the above section, you have gained the step by step process of Dijkstra’s algorithm, now let’s study the
algorithm with an explained example.
We will calculate the shortest path between node C and the other nodes in the graph.

During the execution of the algorithm, each node will be marked with its minimum distance to node C as we
have selected node C.
In this case, the minimum distance is 0 for node C. Also, for the rest of the nodes, as we don’t know this
distance, they will be marked as infinity (∞), except node C (currently marked as red dot).

Graphical Representation of Node C as Current Node

Now the neighbours of node C will be checked, i.e, node A, B, and D. We start with B, here we will add the
minimum distance of current node (0) with the weight of the edge (7) that linked the node C to node B and get
0+ 7= 7.
Now, this value will be compared with the minimum distance of B (infinity), the least value is the one that
remains the minimum distance of B, like in this case, 7 is less than infinity, and marks the least value to node B.

Assign Node B a minimum distance value

Now, the same process is checked with neighbour A. We add 0 with 1 (weight of edge that connects node C to
A), and get 1. Again, 1 is compared with the minimum distance of A (infinity), and marks the lowest value.

Assign Node A a minimum distance value

The same is repeated with node D, and marked 2 as lowest value at D.
Assign Node D a minimum distance value

Since, all the neighbours of node C have checked, so node C is marked as visited with a green check mark.

Marked Node C as visited

Now, we will select the new current node such that the node must be unvisited with the lowest minimum
distance, or the node with the least number and no check mark. Here, node A is the unvisited with minimum
distance 1, marked as current node with red dot and.
 node |predecessor
a | c

Graphical Representation of Node A as Current Node

We repeat the algorithm, checking the neighbour of the current node while ignoring the visited node, so only
node B will be checked.

For node B, we add 1 with 3 (weight of the edge connecting node A to B) and obtain 4. This value, 4, will be
compared with the minimum distance of B, 7, and mark the lowest value at B as 4.

Assign Node B a minimum distance value

After this, node A marked as visited with a green check mark. The current node is selected as node D, it is
unvisited and has a smallest recent distance. We repeat the algorithm and check for node B and E.
node |predecessor
a | c
d | c

Graphical Representation of Node D as Current Node

For node B, we add 2 to 5, get 7 and compare it with the minimum distance value of B, since 7>4, so leave the
smallest distance value at node B as 4.
For node E, we obtain 2+ 7= 9, and compare it with the minimum distance of E which is infinity, and mark the
smallest value as node E as 9. The node D is marked as visited with a green check mark.

Marked Node D as visited

 The current node is set as node B, here we need to check only node E as it is unvisited and the node D is visited.
We obtain 4+ 1=5, compare it with the minimum distance of the node.
As 9 > 5, leave the smallest value at node node E as 5.
We mark D as visited node with a green check mark, and node E is set as the current node.

node |predecessor
a | c
d | c
b | a

Marked Node B as visited

Since it doesn’t have any unvisited neighbours, so there is not any requirement to check anything. Node E is
marked as a visited node with a green mark.

node |predecessor
a | c
d | c
b | a
e | b
Marked Node E as visited
So, we are done as no unvisited node is left. The minimum distance of each node is now representing the
minimum distance of that node from node C. node |predecessor
Now you want to find out the shortest path from c to e . a | c
1)now we try to find out predecessor of e i.e b so b->e d | c
2) next we try to find out predecessor of b i.e a so path is a->b->e b | a
3) next we try to find out predecessor of a i.e c so path is c->a->b->e e | b
Shortest path c->a->b->e And value is 1+3+1=5[c->a=1,a->b=3,b->e=1]
Note : we always start from destination and find out the predecessor of destination or current node.this process
will continue until you reach at source.
Applications of Dijkstra’s Algorithm

For map applications, it is hugely deployed in measuring the least possible distance and check direction
amidst two geographical regions like Google Maps, discovering map locations pointing to the vertices of a
graph, calculating traffic and delay-timing, etc.
For telephone networks, this is also extensively implemented in the conducting of data in networking and
telecommunication domains for decreasing the obstacle taken place for transmission.
Wherever addressing the need for shortest path explications either in the domain of robotics, transport,
embedded systems, laboratory or production plants, etc, this algorithm is applied.
Besides that, other applications are road conditions, road closures and construction, and IP routing to
detect Open Shortest Path First.

Advantages and Disadvantages of Dijkstra’s Algorithm

Discussing some advantages of Dijkstra’s algorithm;

One of the main advantages of it is its little complexity which is almost linear.
It can be used to calculate the shortest path between a single node to all other nodes and a single source node to
a single destination node by stopping the algorithm once the shortest distance is achieved for the destination
node.
It only works for directed-, weighted graphs and all edges should have non-negative values.
Despite various applications and advantages, Dijkstra’s algorithm has disadvantages also, such as;
It does an obscured exploration that consumes a lot of time while processing,
It is unable to handle negative edges,
As it heads to the acyclic graph, so can’t achieve the accurate shortest path, and
Also, there is a need to maintain tracking of vertices, have been visited.
 Topological Sort :

In any directed graph which has no cycle, topological sort gives the sequential order of all the nodes x, y є G
And x comes before y in sequential order if a path exists from x to y. So this sequential order will indicate the
dependency of one task on another.
Adjacency list of G will be –
A <-> B, F
B -> E, F
C -> B, D
D -> B, E
E ->
F ->
G -> E, F
Now we have a need to find the way to get topological sorting. We should first take those nodes which have no
predecessors. It can be chosen very easily. The nodes which have topological sorting can be define as –
1. Take all the nodes which have Zero in degree.
2. Delete those nodes and edges going from those nodes.
3. Do the same process again until all the nodes are deleted.
This operation will need a queue where all the nodes which have in degree zero will be first added then deleted.
Every time we need to get the information of in degree of every node. One array is also required where all the
nodes will be in sequence of deletion from queue. Let us take a graph and find the topological sorting-
Here we are taking a queue for maintaining the zero in degree elements and array topSort for sequence of
deleted elements from queue.
Step1-
In degree of nodes are-A=0,B=3,C=0,D=1,E=3,F=3,G=0

Step2-
i)Taking all the nodes, which have zero in degree.
A,C,G
ii)Add all zero in degree nodes to queue
Queue: A,C,G Front=0 , Rear=2 topSort:
iii) Delete the node A and edges going from A.
Queue: C,G Front=1 , Rear=2 topSort:A
iv)Now the in degree of nodes will be-
B=2,D=1,E=3,F=2

Step3-
i)Delete the node C and edges going from C
Queue: G Front=2 , Rear=2 topSort:A,C
ii)Now the in degree of nodes will be-
B=1,D=0,E=3,F=2
Step4-
i)Add D to queue
Queue: G,D Front=2 , Rear=3 topSort:A,C
ii) Delete the node G and edges going from G.
Queue: D Front=3 , Rear=3 topSort:A,C,G
iv)Now the in degree of nodes will be-
B=1,E=2,F=1

Step5-
i) Delete the node D and edges going from D.
Queue: Front=4 , Rear=3 topSort:A,C,G,D
ii)Now the in degree of nodes will be-
B=0,E=1,F=1

Step6-
i)Add B to queue
Queue: B Front=4 , Rear=4 topSort:A,C,G,D
ii) Delete the node B and edges going from B.
Queue: Front=5 , Rear=4 topSort:A,C,G,D,B
iii)Now the in degree of nodes will be-
E=0,F=1
Step7-
i)Add E to queue
Queue: E Front=5 , Rear=5 topSort:A,C,G,D,B
ii) Delete the node E and edges going from E.
Queue: Front=6 , Rear=5 topSort:A,C,G,D,B,E
iii)Now the in degree of nodes will be-
F=0

Step8-
i)Add F to queue
Queue: F Front=6 , Rear=6 topSort:A,C,G,D,B,E
ii) Delete the node F and edges going from F.
Queue: Front=7 , Rear=6 topSort:A,C,G,D,B,E,F

Now we have no more nodes in the graph. So the topological sorting of graph will be-
A,C,G,D,B,E,F
Algorithm name Time complexity Space complexity
Average Worst Worst
Dijkstra algorithm O(|E|*log |V|) O(|V|2) O(|V|+|E|)
Prims Algorithm O(|E|*log |V|) O(|V|2) O(|V|+|E|)
Krushkal algorithm O(|E|*log |V|) O(|E|*log |V|) O(|V|+|E|)
Topological Sort O(|V|+|E|) O(|V|+|E|) O(|V|+|E|)