Dijkstra Algorithm
Exploring Graph Algorithms : Dijkstra Algorithm
Today, we dive into the fascinating world of Graph algorithms and uncover their most captivating mysteries — Dijkstra Algorithm . Get ready to embark that will challenge your minds and you will come to know about the power of Graphs.
Introduction to Graph Algorithms
Graph algorithms are a powerful tool for solving a wide variety of problems . These are used to solve problems on graphs , such as finding the shortest path between two nodes , finding the maximum flow in a network or detecting communities in a social network.
Graph algorithms are used wide variety of applications such as
 Transportation : for finding the shortest route between two points
 Social Networks : detecting spam users , identifying influential users
 Computer Science : compiling programs , optimizing network performance and malware detection
There are few basic types of algorithms such as “Breadthfirst search(BFS)” , “depthfirst search(DFS)”, Dijkstra algorithm ,BellmanFord algorithm etc. and also we have few advanced type of algorithms such as “Matching algorithm” , “Clustering algorithm”, and Maximum flow algorithm etc. It also works on both directed(edges are present for a graph) and undirected graph(there will be no edges for a graph) .
Graph algorithm can be implemented in different programming languages and software Libraries . Some popular graph libraries include
 NetworkX : A python library for graph implementation and graph manipulation
 GraphLab : A distributed graph computing framework
 Neo4j : A graph database management system
One of the fundamental tasks in graph theory is Dijkstra Algorithm.
Overview of Dijkstra’s Algorithm
Dijkstra’s algorithm is a graph algorithm that finds you the shortest path between a single source node and all other nodes in a graph . It is a greedy algorithm , that it makes the locally optimal choice at each step in order to reach the globally optimal solution.
CODE:
import heapq
def dijkstra(graph, start): # Initialize distances and visited nodes distances = {node: float('infinity') for node in graph} distances[start] = 0 priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
Userdefined graph input
graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1} }
start_node = input("Enter the starting node: ").upper()
Check if the starting node is in the graph
if start_node not in graph: print("Invalid starting node.") else: result = dijkstra(graph, start_node) print("Shortest distances from node {}:".format(start_node)) for node, distance in result.items(): print("To {}: {}".format(node, distance))
Code Explanation :

Initialize a set of visited nodes and a set of unvisited nodes . The visited set is initially empty, and the unvisited set contains all the nodes in the graph .

select the source node and add it into the visited set .

For each neighbor of the source node, calculate the shortest distance from the source node to the neighbor. If the calculated distance is shortest than the current distance sorted for the neighbor , update the neighbor’s distance and add it into the priority queue.

Once all nodes have been visited, the distance of each node is the shortest distance from the source node to that node

Here the algorithm terminates, when all of the nodes in the graph have been visited. At this point , the tentative distance of each node is equal to the shortest distance from the source to that node.
Time Complexity and space complexity :
O(E * logV), Where E is the number of edges and V is the number of vertices.
The time complexity of the given code/algorithm looks O(V^2) as there are two nested while loops. If we take a closer look, we can observe that the statements in inner loop are executed O(V+E) times (similar to BFS). The inner loop has decreaseKey() operation which takes O(LogV) time. So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV) Note that the above code uses Binary Heap for Priority Queue implementation. Time complexity can be reduced to O(E + VLogV) using Fibonacci Heap. The reason is, Fibonacci Heap takes O(1) time for decreasekey operation while Binary Heap takes O(Logn) time.
space complexity is O(V).
TEST CASE  1:
A 2 B  /  3 1 4  /  C 5 D
INPUT:
Start Node: A End Node: D
OUTPUT :
Shortest Path: A > B > D Shortest Distance: 6
TEST CASE 2 :
A 3 B 1 C  /  2 4 5  /  D 7 E 6 F
INPUT:
Start Node: A End Node: F
OUTPUT:
Shortest Path: A > B > C > F Shortest Distance: 10
TEST CASE 3 :
A 1 B 3 C  /  4 2 5  /  D 6 E 7 F
INPUT:
Start Node: A End Node: F
OUTPUT:
Shortest Path: A > B > C > F Shortest Distance: 9