What is Dijkstra's Algorithm? Explanation and Example

Common applications of Dijkstra's algorithm include:

• GPS navigation systems
• Computer network routing
• Game AI pathfinding
• Robotics and autonomous vehicles
• Map-based location recommendation services

1. How It Works

Dijkstra's algorithm is based on a greedy approach and operates in the following steps:

• Set the distance of the starting node to 0, and all other nodes to ∞$\text{(infinity)}$.
• Select the node with the smallest tentative distance $\text{(initially the start node)}$.
• For each neighboring node of the current node:

1) Calculate the tentative distance through the current node.
2) If this new distance is shorter than the currently recorded one, update it.
3) Mark the current node as visited (processed).
4) Repeat steps 2–4 until all nodes have been visited.

Example Graph

             

Graph represented as an edge list:

$\text{A -> B (1), A -> C (4)}$
$\text{B -> C (2), B -> D (5)}$
$\text{C -> D (1)}$
If we want to find the shortest path from node A to all other nodes, Dijkstra's algorithm can be used effectively.

2. Python Code Example

import heapq

def dijkstra(graph, start):
    # Initialize distances from the start node to all others
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # Use a priority queue to keep track of the shortest distances
    queue = [(0, start)]  # (distance, node)

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        # Skip if a better path has already been found
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            # Update the shortest path if a better one is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# Define the graph as an adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

# Run Dijkstra's algorithm
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

# Display results
print(f"Shortest paths from {start_node}:")
for node, dist in shortest_paths.items():
    print(f" - to {node}: {dist}")

Output Explanation

Shortest paths from A:
 - to A: 0
 - to B: 1
 - to C: 3   (A -> B -> C)
 - to D: 4   (A -> B -> C -> D)

3. Time Complexity Analysis

The time complexity of Dijkstra's algorithm depends on the implementation:

• Using a simple array: O(V²)
• Using a binary heap (Python heapq): O((V + E) log V)
• Using a Fibonacci heap (theoretical): O(E + V log V)

In practical Python applications, a binary heap with `heapq` is typically used for optimal performance.

4. Limitations of Dijkstra's Algorithm

• It cannot handle graphs with negative edge weights. Use Bellman-Ford algorithm instead.
• For all-pairs shortest path problems, consider using the Floyd-Warshall algorithm.
• If the graph is dynamically changing, Dijkstra’s precomputed results may become invalid.

5. Comparison with A* Algorithm

The A* algorithm uses a heuristic function to guide the search more efficiently towards the target node, making it faster for single-destination pathfinding. Dijkstra's algorithm, on the other hand, guarantees the shortest path to all nodes and is suitable when the destination is not known in advance.

6. References

• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik, 1(1), 269–271.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
• GeeksforGeeks - Dijkstra’s Algorithm: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-graph-data-structure/
• Python `heapq` documentation: https://docs.python.org/3/library/heapq.html