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.

Directed and Undirected Graph

A graph can be directed or undirected. However, in an undirected graph, edges are
not associated with the directions with them. An undirected graph is shown in the
above figure since its edges are not attached with any of the directions. If an edge
exists between vertex A and B then the vertices can be traversed from B to A as well
as A to B.

In a directed graph, edges form an ordered pair. Edges represent a specific path
from some vertex A to another vertex B. Node A is called initial node while node B is
called terminal node.

A directed graph is shown in the following figure.

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

BFS algorithm
In this article, we will discuss the BFS algorithm in the data structure. Breadth-first
search is a graph traversal algorithm that starts traversing the graph from the root
node and explores all the neighboring nodes. Then, it selects the nearest node and
explores all the unexplored nodes. While using BFS for traversal, any node in the
graph can be considered as the root node.

There are many ways to traverse the graph, but among them, BFS is the most
commonly used approach. It is a recursive algorithm to search all the vertices of a
tree or graph data structure. BFS puts every vertex of the graph into two categories -
visited and non-visited. It selects a single node in a graph and, after that, visits all the
nodes adjacent to the selected node.

Applications of BFS algorithm

The applications of breadth-first-algorithm are given as follows -
 o BFS can be used to find the neighboring locations from a given source
location.
o In a peer-to-peer network, BFS algorithm can be used as a traversal
method to find all the neighboring nodes. Most torrent clients, such as
BitTorrent, uTorrent, etc. employ this process to find "seeds" and
"peers" in the network.
o BFS can be used in web crawlers to create web page indexes. It is one
of the main algorithms that can be used to index web pages. It starts
traversing from the source page and follows the links associated with
the page. Here, every web page is considered as a node in the graph.
o BFS is used to determine the shortest path and minimum spanning tree.
o BFS is also used in Cheney's technique to duplicate the garbage
collection.
o It can be used in ford-Fulkerson method to compute the maximum flow
in a flow network.

Algorithm
The steps involved in the BFS algorithm to explore a graph are given as follows -

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

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS
= 1) and set

their STATUS = 2

Advertisement

(waiting state)

[END OF LOOP]

Step 6: EXIT

Example of BFS algorithm

Now, let's understand the working of BFS algorithm by using an example. In the
example given below, there is a directed graph having 7 vertices.
In the above graph, minimum path 'P' can be found by using the BFS that will start
from Node A and end at Node E. The algorithm uses two queues, namely QUEUE1
and QUEUE2. QUEUE1 holds all the nodes that are to be processed, while
QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.

BFS algorithm
In this article, we will discuss the BFS algorithm in the data structure. Breadth-first
search is a graph traversal algorithm that starts traversing the graph from the root
node and explores all the neighboring nodes. Then, it selects the nearest node and
explores all the unexplored nodes. While using BFS for traversal, any node in the
graph can be considered as the root node.

There are many ways to traverse the graph, but among them, BFS is the most
commonly used approach. It is a recursive algorithm to search all the vertices of a
tree or graph data structure. BFS puts every vertex of the graph into two categories -
visited and non-visited. It selects a single node in a graph and, after that, visits all the
nodes adjacent to the selected node.

Applications of BFS algorithm

The applications of breadth-first-algorithm are given as follows -

o BFS can be used to find the neighboring locations from a given source
location.
o In a peer-to-peer network, BFS algorithm can be used as a traversal
method to find all the neighboring nodes. Most torrent clients, such as
BitTorrent, uTorrent, etc. employ this process to find "seeds" and
"peers" in the network.
o BFS can be used in web crawlers to create web page indexes. It is one
of the main algorithms that can be used to index web pages. It starts
traversing from the source page and follows the links associated with
the page. Here, every web page is considered as a node in the graph.
o BFS is used to determine the shortest path and minimum spanning tree.
 o BFS is also used in Cheney's technique to duplicate the garbage
collection.
o It can be used in ford-Fulkerson method to compute the maximum flow
in a flow network.

Algorithm
The steps involved in the BFS algorithm to explore a graph are given as follows -

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

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

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]

Step 6: EXIT

Example of BFS algorithm

Now, let's understand the working of BFS algorithm by using an example. In the
example given below, there is a directed graph having 7 vertices.

In the above graph, minimum path 'P' can be found by using the BFS that will start
from Node A and end at Node E. The algorithm uses two queues, namely QUEUE1
and QUEUE2. QUEUE1 holds all the nodes that are to be processed, while
QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.
DFS (Depth First Search) algorithm
In this article, we will discuss the DFS algorithm in the data structure. It is a recursive
algorithm to search all the vertices of a tree data structure or a graph. The depth-first
search (DFS) algorithm starts with the initial node of graph G and goes deeper until
we find the goal node or the node with no children.

Because of the recursive nature, stack data structure can be used to implement the
DFS algorithm. The process of implementing the DFS is similar to the BFS algorithm.

The step by step process to implement the DFS traversal is given as follows -

1. First, create a stack with the total number of vertices in the graph.
2. Now, choose any vertex as the starting point of traversal, and push that vertex
into the stack.
3. After that, push a non-visited vertex (adjacent to the vertex on the top of the
stack) to the top of the stack.
4. Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on the
stack's top.
5. If no vertex is left, go back and pop a vertex from the stack.
6. Repeat steps 2, 3, and 4 until the stack is empty.

Applications of DFS algorithm

The applications of using the DFS algorithm are given as follows -

o DFS algorithm can be used to implement the topological sorting.

o It can be used to find the paths between two vertices.
o It can also be used to detect cycles in the graph.
o DFS algorithm is also used for one solution puzzles.
o DFS is used to determine if a graph is bipartite or not.

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

Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until STACK is empty

Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)

Step 5: Push on the stack all the neighbors of N that are in the ready state (whose
STATUS = 1) and set their STATUS = 2 (waiting state)

[END OF LOOP]

Step 6: EXIT
 Example of DFS algorithm
Now, let's understand the working of the DFS algorithm by using an example. In the
example given below, there is a directed graph having 7 vertices.

Now, let's start examining the graph starting from Node H.

Step 1 - First, push H onto the stack.

1. STACK: H
Step 2 - POP the top element from the stack, i.e., H, and print it. Now, PUSH all the
neighbors of H onto the stack that are in ready state.

1. Print: H]STACK: A
Step 3 - POP the top element from the stack, i.e., A, and print it. Now, PUSH all the
neighbors of A onto the stack that are in ready state.

1. Print: A
2. STACK: B, D
Step 4 - POP the top element from the stack, i.e., D, and print it. Now, PUSH all the
neighbors of D onto the stack that are in ready state.

Advertisement

1. Print: D
2. STACK: B, F
Step 5 - POP the top element from the stack, i.e., F, and print it. Now, PUSH all the
neighbors of F onto the stack that are in ready state.

1. Print: F
2. STACK: B
Step 6 - POP the top element from the stack, i.e., B, and print it. Now, PUSH all the
neighbors of B onto the stack that are in ready state.

1. Print: B
2. STACK: C
Step 7 - POP the top element from the stack, i.e., C, and print it. Now, PUSH all the
neighbors of C onto the stack that are in ready state.

Advertisement

1. Print: C
2. STACK: E, G
Step 8 - POP the top element from the stack, i.e., G and PUSH all the neighbors of
G onto the stack that are in ready state.

1. Print: G
2. STACK: E
Step 9 - POP the top element from the stack, i.e., E and PUSH all the neighbors of E
onto the stack that are in ready state.

1. Print: E
2. STACK:

Spanning tree
In this article, we will discuss the spanning tree and the minimum spanning tree. But
before moving directly towards the spanning tree, let's first see a brief description of
the graph and its types.

Graph
A graph can be defined as a group of vertices and edges to connect these vertices.
The types of graphs are given as follows -

o Undirected graph: An undirected graph is a graph in which all the

edges do not point to any particular direction, i.e., they are not
unidirectional; they are bidirectional. It can also be defined as a graph
with a set of V vertices and a set of E edges, each edge connecting two
different vertices.
o Connected graph: A connected graph is a graph in which a path
always exists from a vertex to any other vertex. A graph is connected if
we can reach any vertex from any other vertex by following edges in
either direction.
o Directed graph: Directed graphs are also known as digraphs. A graph
is a directed graph (or digraph) if all the edges present between any
vertices or nodes of the graph are directed or have a defined direction.
Now, let's move towards the topic spanning tree.

What is a 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.

Example of Spanning tree

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

Let's understand the minimum spanning tree with the help of an example.

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 -

Applications of minimum spanning tree

The applications of the minimum spanning tree are given as follows -

o Minimum spanning tree can be used to design water-supply networks,

telecommunication networks, and electrical grids.
o It can be used to find paths in the map.

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
Let's see a brief description of both of the algorithms listed above.

Prim's algorithm - It is a greedy algorithm that starts with an empty spanning tree. It
is used to find the minimum spanning tree from the graph. This 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
In this article, we will discuss the prim's algorithm. Along with the algorithm, we will
also see the complexity, working, example, and implementation of prim's algorithm.

Before starting the main topic, we should discuss the basic and important terms such
as spanning tree and minimum spanning tree.

Spanning tree - A spanning tree is the subgraph of an undirected connected graph.

Minimum Spanning tree - 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.

Now, let's start the main topic.

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 -

Advertisement

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 weight
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 - This algorithm is also used to find the minimum spanning tree
for a connected weighted graph. Kruskal's algorithm also follows greedy approach,
which finds an optimum solution at every stage instead of focusing on a global
optimum.

Kruskal's Algorithm
In this article, we will discuss Kruskal's algorithm. Here, we will also see the
complexity, working, example, and implementation of the Kruskal's algorithm.

But before moving directly towards the algorithm, we should first understand the
basic terms such as spanning tree and minimum spanning tree.

Spanning tree - A spanning tree is the subgraph of an undirected connected graph.

Minimum Spanning tree - 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.

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.

Advertisement

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.

Advertisement

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 sep
arate 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
6. (for combining two trees into one tree).
7. ELSE
8. Discard the edge
9. Step 6: END

Complexity of Kruskal's algorithm

Now, let's see the time complexity of Kruskal's algorithm.

o TimeComplexity
The time complexity of Kruskal's algorithm is O(E logE) or O(V logV),
where E is the no. of edges, and V is the no. of vertices.

Dijkstra's Algorithm
The following tutorial will teach us about Dijkstra's Shortest Path Algorithm. We will
understand the working of Dijkstra's Algorithm with a stepwise graphical explanation.
We will cover the following:

o A Brief Overview of the Fundamental Concepts of Graph

o Understand the Use of Dijkstra's Algorithm
o Understand the Working of the Algorithm with a Step-by-Step Example
So, let's get started.

A Brief Introduction to Graphs

Graphs are non-linear data structures representing the "connections" between the
elements. These elements are known as the Vertices, and the lines or arcs that
connect any two vertices in the graph are known as the Edges. More formally, a
Graph comprises a set of Vertices (V) and a set of Edges (E). The Graph is
denoted by G(V, E).

Backward Skip 10sPlay VideoForward Skip 10s

Components of a Graph
1. Vertices:Vertices are the basic units of the graph used to represent real-life
objects, persons, or entities. Sometimes, vertices are also known as Nodes.
2. Edges:Edges are drawn or used to connect two vertices of the graph.
Sometimes, edges are also known as Arcs.

The following figure shows a graphical representation of a Graph:

Figure 1: Graphical Representation of a Graph

In the above figure, the Vertices/Nodes are denoted with Colored Circles, and the
Edges are denoted with the lines connecting the nodes.

Applications of the Graphs

Graphs are used to solve many real-life problems. Graphs are utilized to represent
the networks. These networks may include telephone or circuit networks or paths in
a city.

For example, we could use Graphs to design a transportation network model where
the vertices display the facilities that send or receive the products, and the edges
represent roads or paths connecting them. The following is a pictorial representation
of the same:

Figure 2: Pictorial Representation of Transportation Network

Graphs are also utilized in different Social Media Platforms like LinkedIn, Facebook,
Twitter, and more. For example, Platforms like Facebook use Graphs to store the
data of their users where every person is indicated with a vertex, and each of them is
a structure containing information like Person ID, Name, Gender, Address, etc.

Types of Graphs
The Graphs can be categorized into two types:

1. Undirected Graph
2. Directed Graph

Undirected Graph: A Graph with edges that do not have a direction is termed an
Undirected Graph. The edges of this graph imply a two-way relationship in which
each edge can be traversed in both directions. The following figure displays a simple
undirected graph with four nodes and five edges.

Figure 3: A Simple Undirected Graph

Directed Graph: A Graph with edges with direction is termed a Directed Graph. The
edges of this graph imply a one-way relationship in which each edge can only be
traversed in a single direction. The following figure displays a simple directed graph
with four nodes and five edges.
Figure 4: A Simple Directed Graph

The absolute length, position, or orientation of the edges in a graph illustration

characteristically does not have meaning. In other words, we can visualize the same
graph in different ways by rearranging the vertices or distorting the edges if the
underlying structure of the graph does not alter.

Advertisement

What are Weighted Graphs?

A Graph is said to be Weighted if each edge is assigned a 'weight'. The weight of an
edge can denote distance, time, or anything that models the 'connection' between
the pair of vertices it connects.

For instance, we can observe a blue number next to each edge in the following
figure of the Weighted Graph. This number is utilized to signify the weight of the
corresponding edge.
Figure 5: An Example of a Weighted Graph

An Introduction to Dijkstra's Algorithm

Now that we know some basic Graphs concepts let's dive into understanding the
concept of Dijkstra's Algorithm.

Ever wondered how does Google Maps finds the shortest and fastest route between
two places?

Well, the answer is Dijkstra's Algorithm. Dijkstra's Algorithm is a Graph

algorithm that finds the shortest path from a source vertex to all other vertices in
the Graph (single source shortest path). It is a type of Greedy Algorithm that only
works on Weighted Graphs having positive weights. The time complexity of Dijkstra's
Algorithm is O(V2) with the help of the adjacency matrix representation of the graph.
This time complexity can be reduced to O((V + E) log V) with the help of an
adjacency list representation of the graph, where V is the number of vertices and E is
the number of edges in the graph.

History of Dijkstra's Algorithm

Dijkstra's Algorithm was designed and published by Dr. Edsger W. Dijkstra, a Dutch
Computer Scientist, Software Engineer, Programmer, Science Essayist, and
Systems Scientist.

During an Interview with Philip L. Frana for the Communications of the ACM
journal in the year 2001, Dr. Edsger W. Dijkstra revealed:

"What is the shortest way to travel from Rotterdam to Groningen, in general: from
given city to given city? It is the algorithm for the shortest path, which I designed in
about twenty minutes. One morning I was shopping in Amsterdam with my young
fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was
just thinking about whether I could do this, and I then designed the algorithm for the
shortest path. As I said, it was a twenty-minute invention. In fact, it was published in
'59, three years later. The publication is still readable, it is, in fact, quite nice. One of
the reasons that it is so nice was that I designed it without pencil and paper. I
learned later that one of the advantages of designing without pencil and paper is that
you are almost forced to avoid all avoidable complexities. Eventually, that algorithm
became to my great amazement, one of the cornerstones of my fame."

Dijkstra thought about the shortest path problem while working as a programmer at
the Mathematical Centre in Amsterdam in 1956 to illustrate the capabilities of a new
computer known as ARMAC. His goal was to select both a problem and a solution
(produced by the computer) that people with no computer background could
comprehend. He developed the shortest path algorithm and later executed it for
ARMAC for a vaguely shortened transportation map of 64 cities in the Netherlands
(64 cities, so 6 bits would be sufficient to encode the city number). A year later, he
came across another issue from hardware engineers operating the next computer of
the institute: Minimize the amount of wire required to connect the pins on the
machine's back panel. As a solution, he re-discovered the algorithm called Prim's
minimal spanning tree algorithm and published it in the year 1959.

Fundamentals of Dijkstra's Algorithm

The following are the basic concepts of Dijkstra's Algorithm:

1. Dijkstra's Algorithm begins at the node we select (the source node), and it
examines the graph to find the shortest path between that node and all the other
nodes in the graph.
2. The Algorithm keeps records of the presently acknowledged shortest distance
from each node to the source node, and it updates these values if it finds any
shorter path.
3. Once the Algorithm has retrieved the shortest path between the source and
another node, that node is marked as 'visited' and included in the path.
4. The procedure continues until all the nodes in the graph have been included in
the path. In this manner, we have a path connecting the source node to all other
nodes, following the shortest possible path to reach each node.

Understanding the Working of Dijkstra's Algorithm

A graph and source vertex are requirements for Dijkstra's Algorithm. This Algorithm
is established on Greedy Approach and thus finds the locally optimal choice (local
minima in this case) at each step of the Algorithm.

Each Vertex in this Algorithm will have two properties defined for it:

1. Visited Property
2. Path Property

Let us understand these properties in brief.

Visited Property:
 1. The 'visited' property signifies whether or not the node has been visited.
2. We are using this property so that we do not revisit any node.
3. A node is marked visited only when the shortest path has been found.

Path Property:
1. The 'path' property stores the value of the current minimum path to the node.
2. The current minimum path implies the shortest way we have reached this node till
now.
3. This property is revised when any neighbor of the node is visited.
4. This property is significant because it will store the final answer for each node.

Initially, we mark all the vertices, or nodes, unvisited as they have yet to be visited.
The path to all the nodes is also set to infinity apart from the source node. Moreover,
the path to the source node is set to zero (0).

We then select the source node and mark it as visited. After that, we access all the
neighboring nodes of the source node and perform relaxation on every node.
Relaxation is the process of lowering the cost of reaching a node with the help of
another node.

In the process of relaxation, the path of each node is revised to the minimum value
amongst the node's current path, the sum of the path to the previous node, and the
path from the previous node to the current node.

Let us suppose that p[n] is the value of the current path for node n, p[m] is the value
of the path up to the previously visited node m, and w is the weight of the edge
between the current node and previously visited one (edge weight between n and
m).

In the mathematical sense, relaxation can be exemplified as:

p[n] = minimum(p[n], p[m] + w)

We then mark an unvisited node with the least path as visited in every subsequent
step and update its neighbor's paths.

We repeat this procedure until all the nodes in the graph are marked visited.

Whenever we add a node to the visited set, the path to all its neighboring nodes also
changes accordingly.

If any node is left unreachable (disconnected component), its path remains 'infinity'.
In case the source itself is a separate component, then the path to all other nodes
remains 'infinity

Algorithm for Dijkstra’s Algorithm:

1. Mark the source node with a current distance of 0 and the rest
with infinity.
2. Set the non-visited node with the smallest current distance as the
current node.
3. For each neighbor, N of the current node adds the current
distance of the adjacent node with the weight of the edge
connecting 0->1. If it is smaller than the current distance of Node,
set it as the new current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.

Dijkstra’s shortest path algorithm is similar to that of Prim’s algorithm as

they both rely on finding the shortest path locally to achieve the global
solution. However, unlike prim’s algorithm, the dijkstra’s algorithm does
not find the minimum spanning tree; it is designed to find the shortest
path in the graph from one vertex to other remaining vertices in the
graph. Dijkstra’s algorithm can be performed on both directed and
undirected graphs.

Since the shortest path can be calculated from single source vertex to all
the other vertices in the graph, Dijkstra’s algorithm is also called single-
source shortest path algorithm. The output obtained is called shortest path
spanning tree.

In this chapter, we will learn about the greedy approach of the dijkstra’s
algorithm.

Dijkstra’s Algorithm
The dijkstra’s algorithm is designed to find the shortest path between two
vertices of a graph. These two vertices could either be adjacent or the
farthest points in the graph. The algorithm starts from the source. The
inputs taken by the algorithm are the graph G {V, E}, where V is the set
of vertices and E is the set of edges, and the source vertex S. And the
output is the shortest path spanning tree.

Algorithm
 Declare two arrays − distance[] to store the distances from the
source vertex to the other vertices in graph and visited[] to store
the visited vertices.
 Set distance[S] to ‘0’ and distance[v] = ∞, where v represents all
the other vertices in the graph.
 Add S to the visited[] array and find the adjacent vertices of S with
the minimum distance.
 The adjacent vertex to S, say A, has the minimum distance and is
not in the visited array yet. A is picked and added to the visited
 array and the distance of A is changed from ∞ to the assigned
distance of A, say d1, where d1 < ∞.
 Repeat the process for the adjacent vertices of the visited vertices
until the shortest path spanning tree is formed.

Examples
To understand the dijkstra’s concept better, let us analyze the algorithm
with the help of an example graph −

Step 1

Initialize the distances of all the vertices as ∞, except the source node S.

Vertex S A B C D E

Distance 0 ∞ ∞ ∞ ∞ ∞

Now that the source vertex S is visited, add it into the visited array.

visited = {S}

Step 2
The vertex S has three adjacent vertices with various distances and the
vertex with minimum distance among them all is A. Hence, A is visited
and the dist[A] is changed from ∞ to 6.

S→A=6
S→D=8
S→E=7
Vertex S A B C D E

Distance 0 6 ∞ ∞ 8 7

Visited = {S, A}

Step 3

There are two vertices visited in the visited array, therefore, the adjacent
vertices must be checked for both the visited vertices.

Vertex S has two more adjacent vertices to be visited yet: D and E.

Vertex A has one adjacent vertex B.

Calculate the distances from S to D, E, B and select the minimum distance

−

S → D = 8 and S → E = 7.
S → B = S → A + A → B = 6 + 9 = 15
Vertex S A B C D E
Distance 0 6 15 ∞ 8 7

Visited = {S, A, E}

Step 4

Calculate the distances of the adjacent vertices – S, A, E – of all the

visited arrays and select the vertex with minimum distance.

S→D=8
S → B = 15
S → C = S → E + E → C = 7 + 5 = 12
Vertex S A B C D E

Distance 0 6 15 12 8 7

Visited = {S, A, E, D}
Step 5

Recalculate the distances of unvisited vertices and if the distances

minimum than existing distance is found, replace the value in the distance
array.

S → C = S → E + E → C = 7 + 5 = 12
S → C = S → D + D → C = 8 + 3 = 11

dist[C] = minimum (12, 11) = 11

S → B = S → A + A → B = 6 + 9 = 15
S → B = S → D + D → C + C → B = 8 + 3 + 12 = 23

dist[B] = minimum (15,23) = 15

Vertex S A B C D E

Distance 0 6 15 11 8 7

Visited = { S, A, E, D, C}
Step 6

The remaining unvisited vertex in the graph is B with the minimum

distance 15, is added to the output spanning tree.

Visited = {S, A, E, D, C, B}
The shortest path spanning tree is obtained as an output using the
dijkstra’s algorithm.