Skip to main content
This module implements Dijkstra’s algorithm for finding shortest paths in weighted graphs.

​
Functions

​
shortest_path

Computes weight and predecessor tables using Dijkstra’s algorithm. 
from dsa.dijkstra import shortest_path

weight_table, predecessor = shortest_path(graph, start, end, debug=False)
​
graph
Graph
required
The graph to search (must have adjacent_items() method for weighted edges)
​
start
str
required
The starting vertex label
​
end
str
required
The ending vertex label
​
debug
bool
default:"False"
If True, displays the weight table as it is being built during the algorithm execution
​
weight_table
dict
Dictionary mapping vertices to their shortest distance from the start vertex
​
predecessor
dict
Dictionary mapping each vertex to its predecessor in the shortest path from start
Raises:
  • KeyError: If start or end vertex is not in the graph
from dsa.graph import AdjacencyListWeightedGraph
from dsa.dijkstra import shortest_path

# Create a weighted graph
graph = AdjacencyListWeightedGraph()
graph.add_edge("A", "B", 4)
graph.add_edge("A", "C", 2)
graph.add_edge("B", "C", 1)
graph.add_edge("B", "D", 5)
graph.add_edge("C", "D", 8)

# Get weight and predecessor tables
weights, predecessors = shortest_path(graph, "A", "D")
print(weights)  # {'A': 0, 'C': 2, 'B': 3, 'D': 8}
print(predecessors)  # {'A': 'A', 'C': 'A', 'B': 'C', 'D': 'B'}

​
find_path

Finds the shortest path between two vertices using Dijkstra’s algorithm. 
from dsa.dijkstra import find_path

path = find_path(graph, start, end, debug=False)
​
graph
Graph
required
The graph to search (must have adjacent_items() method for weighted edges)
​
start
str
required
The starting vertex label
​
end
str
required
The ending vertex label
​
debug
bool
default:"False"
If True, displays the weight table, predecessor table, and shortest path weight
​
path
list
List of vertices forming the shortest path from start to end
Raises:
  • KeyError: If start or end vertex is not in the graph, or if there is no path from start to end
from dsa.graph import AdjacencyListWeightedGraph
from dsa.dijkstra import find_path

# Create a weighted graph
graph = AdjacencyListWeightedGraph()
graph.add_edge("A", "B", 4)
graph.add_edge("A", "C", 2)
graph.add_edge("B", "C", 1)
graph.add_edge("B", "D", 5)
graph.add_edge("C", "D", 8)

# Find shortest path
path = find_path(graph, "A", "D")
print(path)  # ['A', 'C', 'B', 'D']
Time Complexity: O((V + E) log V) where V is the number of vertices and E is the number of edgesSpace Complexity: O(V) for storing the weight table, predecessor table, and priority queueThe algorithm uses a min-heap priority queue to efficiently select the next vertex with minimum distance.

Build docs developers (and LLMs) love

Get started for freeTalk to us