Python Program to Find Shortest Path in Graph

Use Dijkstra's algorithm in Python with a priority queue to find the shortest path; for example, use heapq to pick the next closest node and update distances until the destination is reached.

Examples

Inputgraph = {0: {1: 4, 2: 1}, 1: {3: 1}, 2: {1: 2, 3: 5}, 3: {}}; start=0; end=3

OutputShortest path: [0, 2, 1, 3], Distance: 4

Inputgraph = {0: {1: 1}, 1: {2: 2}, 2: {3: 3}, 3: {}}; start=0; end=3

OutputShortest path: [0, 1, 2, 3], Distance: 6

Inputgraph = {0: {}, 1: {0: 1}}; start=0; end=1

OutputNo path found

How to Think About It

To find the shortest path, start from the source node and explore neighbors with the smallest known distance first. Keep track of the shortest distance to each node and update it if a shorter path is found. Continue until you reach the destination or have checked all reachable nodes.

Algorithm

1

Initialize distances to all nodes as infinity except the start node which is zero.

2

Use a priority queue to select the node with the smallest distance.

3

For the selected node, update the distances of its neighbors if a shorter path is found.

4

Keep track of the path by storing the previous node for each visited node.

5

Repeat until the destination node is reached or all nodes are processed.

6

Reconstruct the shortest path from the destination back to the start using the stored previous nodes.

Code

python

import heapq

def dijkstra(graph, start, end):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}

    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_node == end:
            break
        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
                previous[neighbor] = current_node
                heapq.heappush(queue, (distance, neighbor))

    path, node = [], end
    while node is not None:
        path.append(node)
        node = previous[node]
    path.reverse()

    if distances[end] == float('inf'):
        return "No path found"
    return f"Shortest path: {path}, Distance: {distances[end]}"

# Example usage
graph = {0: {1: 4, 2: 1}, 1: {3: 1}, 2: {1: 2, 3: 5}, 3: {}}
print(dijkstra(graph, 0, 3))

Output

Shortest path: [0, 2, 1, 3], Distance: 4

Dry Run

Let's trace the example graph {0: {1:4, 2:1}, 1: {3:1}, 2: {1:2, 3:5}, 3: {}} from start=0 to end=3 through the code.

1

Initialize distances and queue

distances = {0:0, 1:inf, 2:inf, 3:inf}, queue = [(0,0)], previous = {0:None,1:None,2:None,3:None}

2

Pop node 0 from queue

current_node=0, current_distance=0; neighbors: 1 (weight 4), 2 (weight 1)

3

Update neighbors of 0

distances[1]=4, previous[1]=0; distances[2]=1, previous[2]=0; queue=[(1,2),(4,1)]

4

Pop node 2 from queue

current_node=2, current_distance=1; neighbors: 1 (weight 2), 3 (weight 5)

5

Update neighbors of 2

distance to 1 via 2 = 3 < 4, update distances[1]=3, previous[1]=2; distance to 3 = 6; queue=[(3,1),(4,1),(6,3)]

6

Pop node 1 from queue

current_node=1, current_distance=3; neighbor: 3 (weight 1)

7

Update neighbor 3

distance to 3 via 1 = 4 < 6, update distances[3]=4, previous[3]=1; queue=[(4,1),(6,3),(4,3)]

8

Pop node 1 from queue (distance 4)

current_distance=4 > distances[1]=3, skip

9

Pop node 3 from queue

current_node=3, current_distance=4; reached destination, stop

10

Reconstruct path

path = [3], previous[3]=1; path = [3,1], previous[1]=2; path = [3,1,2], previous[2]=0; path = [3,1,2,0]; reverse to [0,2,1,3]

Iteration	Current Node	Distances	Queue	Previous
1	0	{0:0,1:inf,2:inf,3:inf}	[(0,0)]	{0:None,1:None,2:None,3:None}
2	0	{0:0,1:4,2:1,3:inf}	[(1,2),(4,1)]	{0:None,1:0,2:0,3:None}
3	2	{0:0,1:4,2:1,3:inf}	[(3,1),(4,1),(6,3)]	{0:None,1:0,2:0,3:None}
4	2	{0:0,1:3,2:1,3:6}	[(3,1),(4,1),(6,3)]	{0:None,1:2,2:0,3:None}
5	1	{0:0,1:3,2:1,3:6}	[(4,1),(6,3),(4,3)]	{0:None,1:2,2:0,3:None}
6	1	{0:0,1:3,2:1,3:4}	[(4,1),(6,3),(4,3)]	{0:None,1:2,2:0,3:1}
7	3	{0:0,1:3,2:1,3:4}	[(6,3),(4,3)]	{0:None,1:2,2:0,3:1}

Why This Works

Step 1: Initialize distances

Set all node distances to infinity except the start node which is zero to mark it as the starting point.

Step 2: Use priority queue

Select the node with the smallest current distance to explore next, ensuring the shortest paths are found first.

Step 3: Update neighbors

For each neighbor, calculate the new distance and update if it is shorter than the previously known distance.

Step 4: Reconstruct path

Trace back from the destination node to the start node using stored previous nodes to get the shortest path.

Alternative Approaches

Breadth-First Search (BFS) for unweighted graphs

python

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = set()
    while queue:
        current, path = queue.popleft()
        if current == end:
            return f"Shortest path: {path}, Distance: {len(path)-1}"
        visited.add(current)
        for neighbor in graph.get(current, {}):
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))
    return "No path found"

# Example usage
graph = {0: {1:1, 2:1}, 1: {3:1}, 2: {1:1, 3:1}, 3: {}}
print(bfs_shortest_path(graph, 0, 3))

BFS works only for graphs where all edges have equal weight; it is simpler but not suitable for weighted graphs.

Bellman-Ford algorithm

python

def bellman_ford(graph, start, end):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, w in graph[u].items():
                if distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w
                    previous[v] = u
    path, node = [], end
    while node is not None:
        path.append(node)
        node = previous[node]
    path.reverse()
    if distances[end] == float('inf'):
        return "No path found"
    return f"Shortest path: {path}, Distance: {distances[end]}"

# Example usage
graph = {0: {1: 4, 2: 1}, 1: {3: 1}, 2: {1: 2, 3: 5}, 3: {}}
print(bellman_ford(graph, 0, 3))

Bellman-Ford handles graphs with negative weights but is slower than Dijkstra's algorithm.

Complexity: O(E log V) time, O(V) space

Time Complexity

Dijkstra's algorithm runs in O(E log V) time using a priority queue, where E is edges and V is vertices, because each edge is processed and the queue operations take log V time.

Space Complexity

It uses O(V) space to store distances, previous nodes, and the priority queue.

Which Approach is Fastest?

Dijkstra with a priority queue is faster than Bellman-Ford for graphs without negative weights; BFS is fastest but only works for unweighted graphs.

Approach	Time	Space	Best For
Dijkstra's Algorithm	O(E log V)	O(V)	Weighted graphs with non-negative edges
Breadth-First Search (BFS)	O(V + E)	O(V)	Unweighted graphs
Bellman-Ford Algorithm	O(VE)	O(V)	Graphs with negative weights