Simon Vitt

What is Dijkstra's Algorithm?

Dijkstra's algorithm is a greedy graph search algorithm that finds the shortest path from a starting node to all other nodes in a weighted graph. Developed by Dutch computer scientist Edsger W. Dijkstra in 1956, it's one of the most fundamental algorithms in computer science and graph theory.

How It Works

The algorithm maintains a set of unvisited nodes and iteratively selects the node with the smallest known distance from the start:

Initialize all nodes with distance ∞, except the start node (distance 0)
Mark the start node as current and visit all its neighbors
Update neighbor distances if a shorter path is found
Mark the current node as visited and select the unvisited node with the smallest distance
Repeat until all reachable nodes are visited

Implementation

Here's a Python implementation using a priority queue:

from typing import Dict, List, Tuple
import heapq

def dijkstra(graph: Dict[str, List[Tuple[str, float]]], start: str) -> Dict[str, float]:
    """
    Find shortest paths from a start node to all other nodes in a weighted graph.
    
    Uses Dijkstra's algorithm with a priority queue to efficiently find the minimum
    distance paths. Works for graphs with non-negative edge weights.
    
    Args:
        graph: Adjacency list representation. Each node maps to a list of (neighbor, weight) tuples.
        start: Starting node identifier.
    
    Returns:
        Dictionary mapping each node to its shortest distance from the start node.
        Unreachable nodes will have distance float('inf').
    
    Time Complexity: O((V + E) log V) where V is vertices and E is edges.
    Space Complexity: O(V) for distances and priority queue.
    """
    distances: Dict[str, float] = {node: float('inf') for node in graph}
    distances[start] = 0.0
    pq: List[Tuple[float, str]] = [(0.0, start)]
    visited: set[str] = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        if current in visited:
            continue
        visited.add(current)
        
        for neighbor, weight in graph[current]:
            if neighbor not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
    
    return distances

# Example
graph = {'A': [('B', 4), ('C', 2), ('E', 8)], 'B': [('C', 1)],
         'C': [('D', 3), ('E', 3)], 'D': [('E', 1)], 'E': [('A', 4)]}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 4, 'C': 2, 'D': 5, 'E': 5}

Time Complexity

The time complexity is O((V + E) log V) using a priority queue, where V is the number of vertices and E is the number of edges. This makes it efficient for finding shortest paths in graphs with non-negative edge weights.

Real-World Applications

GPS navigation systems: finding the fastest route between locations
Network routing: determining optimal paths in computer networks
Social networks: finding shortest connection paths between users
Game development: pathfinding for AI characters
Resource allocation: optimizing distribution in logistics