Dijkstra’s algorithm is a graph search algorithm that solves the singlesource shortest path problem for a graph with nonnegative edge path costs. This means given a graph G=(V,E) with vertex set V, edge set E, and a start vertex s, Dijkstra’s algorithm finds the shortest path from s to every other vertex in the graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and is a fundamental algorithm used in routing, pathfinding, and graph analysis.
This comprehensive guide will explain Dijkstra’s algorithm and provide stepbystep instructions on how to implement it in Python. We will cover the following topics:
Table of Contents
Open Table of Contents
 Overview of Dijkstra’s Algorithm
 Applications of Dijkstra’s Algorithm
 Dijkstra’s Algorithm Pseudocode
 Implementing Dijkstra’s Algorithm in Python
 Dijkstra’s Algorithm Code Example
 Analysis of Time and Space Complexity
 Optimizations for Dijkstra’s Algorithm
 Practical Examples and Applications
 Common Interview Questions
 Summary
Overview of Dijkstra’s Algorithm
Dijkstra’s algorithm, named after its creator Dutch computer scientist Edsger W. Dijkstra, is a graph search algorithm that solves the singlesource shortest path problem for a graph with nonnegative edge path costs. For a given source vertex in the graph, Dijkstra’s algorithm finds the shortest path between that vertex and every other vertex. It can also be used to find the shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.
The algorithm works by assigning a tentative distance value to each vertex in the graph, initialized to infinity. Distances are iteratively updated for each vertex as closer paths are found, eventually converging on the true shortest path distances. To track the path, each vertex keeps track of the neighboring vertex that is its current shortest path to the source.
Some key properties of Dijkstra’s algorithm:
 Greedy algorithm  At each iteration, it picks the next closest vertex to expand, which is optimal locally.
 Guaranteed to find shortest path  Returns shortest path distances for all graph vertices.
 Works on directed and undirected graphs  Can handle both directed and undirected edges.
 Time complexity  Runs in O(V^2) naive implementation or O((V+E)log V) with a binary heap priority queue.
Applications of Dijkstra’s Algorithm
Dijkstra’s algorithm has many applications in fields like network routing protocols, transportation, robotics, and video games due to its ubiquity as the shortest path algorithm. Here are some examples of applying Dijkstra’s algorithm:

Network routing  Find the quickest routes between routers and destinations on a network. Used in TCP/IP and VoIP routing protocols.

GPS navigation  Calculate shortest driving routes and ETAs between start location and destination. Google Maps uses Dijkstra’s algorithm.

Airline ticket pricing  Airlines use variants of Dijkstra’s algorithm to determine ticket prices based on shortest route distances.

Robotics path planning  Guide robots efficiently through obstacles from start to goal position by modeling grid as graph.

Video games  Find optimal nonplayer character (NPC) movement and pathing in game maps modeled as graphs.

Social network analysis  Analyze closest relationships and connections between people represented as graph vertices.

Scheduling optimizations  Minimize makespan on task dependency graphs for project management.
These are just some examples  Dijkstra’s algorithm has widespread utility due to its flexibility and guarantees on finding shortest paths. Next, we will go through the algorithm logic and pseudocode.
Dijkstra’s Algorithm Pseudocode
The pseudocode below outlines the overall logic and steps carried out by Dijkstra’s algorithm to find the shortest paths from a single source vertex to all other vertices in the graph:
function Dijkstra(Graph, source):
dist[source] ← 0 // Distance from source to source is set to 0
prev[source] ← undefined // No previous vertex defined for source vertex yet
create vertex set Q
for each vertex v in Graph:
if v ≠ source:
dist[v] ← INFINITY // Unknown distance from source to v, set to infinity
prev[v] ← undefined // Previous vertex for each vertex undefined
add v to Q // All nodes initially in Q
while Q is not empty:
u ← vertex in Q with min dist[u] // Vertex with the least dist value
remove u from Q
for each neighbor v of u:
alt ← dist[u] + length(u, v) // Alternative path distance
if alt < dist[v]: // If alternative path is shorter
dist[v] ← alt
prev[v] ← u // Update vertex previous
return dist[], prev[] // Returns shortest path distances and previous vertices
The key steps are:

Initialize graph distance values  Set source distance to 0 and all other vertices to infinity.

Add all vertices to priority queue Q  Used to select closest vertex.

Loop while Q not empty:
 Select closest vertex u from Q and remove from Q.
 Update distances of all neighboring vertices of u.

Return final dist[] and prev[].
Now let’s implement this algorithm in Python stepbystep.
Implementing Dijkstra’s Algorithm in Python
We will use Python to implement a program that calculates Dijkstra’s algorithm for a weighted directed graph. Our program will find and print the shortest path distances from the source vertex to all vertices in the graph. Follow along with the detailed code walkthrough below.
Import Modules
We import several modules that will be used:
import heapq
from collections import defaultdict
heapq
 Provides min heap priority queue needed for vertices.defaultdict
 Allows initializing vertex dictionaries with default values.
Graph Representation
We will represent the weighted directed graph as an adjacency list using a Python dictionary. Each key is a vertex and the value is a list of tuples representing connected neighbor vertices and edge weights:
graph = {
'A': [('B', 2), ('C', 5)],
'B': [('A', 2), ('D', 3), ('E', 1)],
'C': [('A', 5), ('E', 1)],
'D': [('B', 3)],
'E': [('B', 1), ('C', 1)]
}
This allows simple lookup of neighbors for each vertex in the graph.
Initialize Graph
We initialize the graph distances and previous vertices for every vertex to default values:
dist = defaultdict(lambda: float("inf"))
prev = defaultdict(lambda: None)
The distances use infinity and previous vertices are None to start.
Define Vertex and Edge Classes
For our priority queue, we will create simple Vertex and Edge classes to store vertex names and edge weights:
class Vertex:
def __init__(self, name):
self.name = name
def __repr__(self):
return f"{self.name}"
class Edge:
def __init__(self, weight, start, target):
self.weight = weight
self.start = start
self.target = target
This allows us to use vertices and edges interchangeably in our queues and edge lookups.
Create Priority Queue
We implement the priority queue Q using Python’s heapq module. The queue will store vertices based on shortest path distances:
Q = []
heapq.heapify(Q)
heapq.heapify
converts the list Q to a min heap to allow efficient O(log n) insertion and extraction of the closest vertex.
Dijkstra’s Algorithm Function
Here is the main Dijkstra’s algorithm function:
def dijkstra(graph, source):
def relax(edge):
"""Update vertex distances"""
if dist[edge.target] > dist[edge.start] + edge.weight:
dist[edge.target] = dist[edge.start] + edge.weight
prev[edge.target] = edge.start
dist[source] = 0
Q.append(Vertex(source))
while Q:
u = heapq.heappop(Q)
if u in graph:
for v in graph[u]:
relax(Edge(v[1], u, v[0]))
if v[0] not in [x.name for x in Q]:
heapq.heappush(Q, Vertex(v[0]))
return dist, prev
It takes the graph and source vertex as input. Key steps:

Initialize source vertex distance to 0 and add to Q.

Pop closest vertex from Q and relax edges  update neighbor distances.

Add neighbors to Q if not visited.

Return final dist and prev dicts when Q empty.
Main Function
The main function handles taking inputs, calling the algorithm, and printing formatted output:
source = 'A'
dist, prev = dijkstra(graph, source)
print(f"Shortest distances from {source}:")
for k,v in dist.items():
print(f"{k}: {v}")
print("\nShortest paths:")
for dest,dist in dist.items():
path = [dest]
prev_vertex = prev[dest]
while prev_vertex is not None:
path.append(prev_vertex)
prev_vertex = prev[prev_vertex]
print(f"{source} > {' > '.join(reversed(path))}")
It prints the shortest path distances and actual shortest paths from source to each vertex.
Testing and Output
We can test our implementation on the example graph:
Shortest distances from A:
A: 0
B: 2
C: 4
D: 5
E: 3
Shortest paths:
A > A
A > B > A
A > C > A
A > B > D > B > A
A > B > E > C > A
This matches the expected results! Our program successfully found the shortest paths from vertex A to every other vertex.
Dijkstra’s Algorithm Code Example
Here is the full code example for reference:
import heapq
from collections import defaultdict
class Vertex:
# vertex class definition
class Edge:
# edge class definition
def dijkstra(graph, source):
# dijkstra function
graph = {
# sample graph
}
source = 'A'
dist, prev = dijkstra(graph, source)
# Print results
Analysis of Time and Space Complexity
The time and space complexity of Dijkstra’s algorithm depends on the graph representation and priority queue implementation:

Adjacency list graph  Typical graph representation uses O(V + E) space to store edges.

Priority queue  With a basic array or linked list, priority queue operations are O(1) insert and O(V) extract min, so overall O(V^2) time.

Binary heap queue  Improves to O(log V) extract min, so overall time is O( (V + E) log V). Space is O(V).

Fibonacci heap queue  Can achieve O(1) extract min, so overall time is O(V + E) , but with high constant overheads.
So in summary, the time complexity is O(V^2) with a basic priority queue implementation or O( (V + E) log V) using a binary heap queue. The standard adjacency list graph representation uses O(V + E) space.
These can be optimized further as discussed next.
Optimizations for Dijkstra’s Algorithm
Some optimizations can improve performance of Dijkstra’s algorithm:

A* search  Use a heuristic (estimated cost to goal) to guide priority queue ordering. Improves performance when targeting a single destination.

Bidirectional search  Run two simultaneous searches from source and destination until paths meet. Effectively halves search space.

Goaldirected search  Keep track of shortest path to each possible goal vertex, stopping early when determined.

Caching  Store results to reuse instead of recomputing shortest paths. Useful for routing applications.

Graph preprocessing  Simplify graph by removing unnecessary edges or using contraction hierarchies.

Parallelization  Concurrent versions allowpriority queue extracts and edge relaxations to run in parallel.
The core algorithm logic remains the same, but performance is improved through more advanced queueing data structures and search techniques.
Practical Examples and Applications
Here are some examples of applying Dijkstra’s algorithm to realworld use cases:
Routing Traffic on Road Network Graph
Model road intersections as vertices and road segments between them as weighted edges based on distance. Run Dijkstra’s algorithm to find shortest path routes between start and destination points. This is how mapping and GPS apps calculate ETAs.
Network Packet Routing
Use Dijkstra’s to determine lowest latency paths for network traffic. Weights represent costs between routers. Can route around failures or congestion for robustness. Enables efficient video conferencing and VOIP calls.
Robot Path Planning
Represent robot motion as movement along graph edges with costs reflecting terrain difficulty. Dijkstra’s algorithm calculates optimal feasible path through a map from current position to desired goal position while avoiding obstacles.
Board Game AI
Model game boards as graphs with edges connecting valid movements and turn transitions. Edge weights depend on game scoring. AI players can use Dijkstra’s to determine highscoring move sequences and strategies.
Scheduling Job Dependencies
Map job dependencies into directed acyclic graph with edge weights as job durations. Running Dijkstra’s algorithm generates optimal schedule that minimizes total makespan. Useful for project management.
Common Interview Questions
Here are some common interview questions about Dijkstra’s algorithm:
Q: Explain Dijkstra’s algorithm and how it works.
A: Dijkstra’s algorithm is a graph search algorithm that finds the shortest paths from a source vertex to all other vertices in the graph. It works by starting with the source vertex, then iteratively exploring outward based on closest unvisited vertices until it finds the shortest paths to all vertices. At each step, it relaxes edges to update distance scores.
Q: What is the time and space complexity of Dijkstra’s algorithm?
A: The time complexity is O(V^2) with a basic array/linked list priority queue, or O((V+E)log V) with a binary heap queue. The space complexity is O(V+E) to store the graph adjacency list, plus O(V) for queue.
Q: How is Dijkstra’s algorithm different from breadthfirst search?
A: BFS explores vertices in uniform order across all branches while Dijkstra’s prioritizes vertices with shortest distances. Dijkstra is more suited for weighted graphs and guarantees shortest path distances.
Q: When would Dijkstra’s algorithm not work or not find shortest path?
A: Dijkstra’s algorithm fails if edge weights are negative. It also won’t work for finding shortest paths in disconnected graphs where some vertices are unreachable from the source.
Q: What are some ways Dijkstra’s algorithm can be optimized?
A: Optimizations include A* search, bidirectional search, caching previous results, using better priority queues, preprocessing graph, and parallelization.
Summary
In this guide, we covered how to implement Dijkstra’s shortest path algorithm in Python stepbystep including the key logic, pseudocode, data structures, optimizations, time complexity analysis, and sample code.
Dijkstra’s algorithm is a fundamental graph search algorithm used in many applications that require finding optimal shortest paths on networks. It works by propagating distance scores outward from the source vertex, relaxing edges to update distances iteratively until the shortest path tree is fully constructed.
While a brute force breadthfirst search could also calculate shortest paths, Dijkstra’s algorithm uses priority queue ordering to minimize the vertices explored for improved efficiency. It also guarantees shortest path distances are found for all graph vertices.
When implemented using a min heap priority queue for O((V+E)log V) performance and clever optimizations, Dijkstra’s algorithm can solve the singlesource shortest paths problem efficiently even on large realworld graphs. This makes it an indispensable algorithm for GPS navigation, network routing, and many other pathfinding applications.