Python Program to Implement Dijkstra Algorithm

You can implement Dijkstra's algorithm in Python using a priority queue with heapq to find the shortest path by updating distances and visiting nodes with the smallest current distance.

Examples

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

Output{0: 0, 1: 3, 2: 1, 3: 4}

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

Output{0: 0, 1: 10, 2: 15, 3: 16}

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

Output{0: 0, 1: inf}

How to Think About It

Think of the graph as a map with cities connected by roads with distances. Start at the source city and always pick the closest city you haven't visited yet. Update the shortest known distances to its neighbors. Repeat until all cities are visited or no closer city remains.

Algorithm

1

Set the distance to the start node as 0 and all others as infinity.

2

Create a priority queue and add the start node with distance 0.

3

While the queue is not empty, remove the node with the smallest distance.

4

For each neighbor of this node, calculate the distance through this node.

5

If this new distance is smaller, update the neighbor's distance and add it to the queue.

6

Repeat until all nodes are processed or the queue is empty.

Code

python

import heapq

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

    while queue:
        current_distance, current_node = heapq.heappop(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(queue, (distance, neighbor))
    return distances

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

Output

{0: 0, 1: 3, 2: 1, 3: 4}

Dry Run

Let's trace the example graph {0: {1: 4, 2: 1}, 1: {3: 1}, 2: {1: 2, 3: 5}, 3: {}} starting from node 0.

1

Initialize distances and queue

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

2

Pop node 0 with distance 0

Check neighbors 1 and 2: update distances to 4 and 1, queue = [(1, 2), (4, 1)]

3

Pop node 2 with distance 1

Check neighbors 1 and 3: update distances to 3 (1+2) and 6 (1+5), queue = [(3, 1), (4, 1), (6, 3)]

4

Pop node 1 with distance 3

Check neighbor 3: update distance to 4 (3+1), queue = [(4, 1), (6, 3), (4, 3)]

5

Pop node 1 with distance 4 (skip)

Distance 4 > known 3, skip

6

Pop node 3 with distance 4

No neighbors, done

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

Why This Works

Step 1: Initialize distances

Set all node distances to infinity except the start node which is zero, so we know where to begin.

Step 2: Use priority queue

Always pick the node with the smallest current distance to explore next, ensuring shortest paths.

Step 3: Update neighbors

If going through the current node gives a shorter path to a neighbor, update that neighbor's distance.

Step 4: Repeat until done

Continue until all nodes are processed or no closer nodes remain, ensuring shortest paths to all.

Alternative Approaches

Using simple list instead of priority queue

python

def dijkstra_simple(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    while len(visited) < len(graph):
        unvisited_nodes = {node: distances[node] for node in graph if node not in visited}
        current_node = min(unvisited_nodes, key=unvisited_nodes.get)
        visited.add(current_node)
        for neighbor, weight in graph[current_node].items():
            if neighbor not in visited:
                new_distance = distances[current_node] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
    return distances

print(dijkstra_simple({0: {1: 4, 2: 1}, 1: {3: 1}, 2: {1: 2, 3: 5}, 3: {}}, 0))

Simpler but slower for large graphs because it scans all nodes to find the minimum distance each time.

Using networkx library

python

import networkx as nx
G = nx.DiGraph()
G.add_weighted_edges_from([(0,1,4),(0,2,1),(2,1,2),(1,3,1),(2,3,5)])
lengths = nx.single_source_dijkstra_path_length(G, 0)
print(lengths)

Uses a popular graph library for easy implementation but requires external dependency.

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

Time Complexity

Using a priority queue, each node is processed once and edges are checked, with heap operations costing log V, leading to O((V + E) log V).

Space Complexity

Stores distances and priority queue data for all nodes, so O(V) space is needed.

Which Approach is Fastest?

Using a priority queue is faster than scanning all nodes for minimum distance, especially on large graphs. Libraries like networkx simplify code but add dependency overhead.

Approach	Time	Space	Best For
Priority Queue (heapq)	O((V + E) log V)	O(V)	Large graphs, efficient
Simple List Scan	O(V^2)	O(V)	Small graphs, simple code
networkx Library	Depends on implementation	Depends on implementation	Quick prototyping, complex graphs