Dijkstra's Shortest Path Visualization

Classic single-source shortest path algorithm

Dijkstra's algorithm finds shortest paths from a source vertex to all other vertices in a weighted graph. It uses a greedy strategy, always expanding the unvisited vertex with minimum current distance.

Distance Table
Click 'Start' to view animation

Algorithm Steps

  1. Initialize: source distance = 0, all other nodes = infinity
  2. Add the source to a priority queue (min-heap)
  3. Extract the node u with the smallest distance from the queue
  4. For each neighbor v of u, if the path through u is shorter, update v's distance
  5. Add the updated neighbor to the priority queue
  6. Repeat steps 3-5 until the queue is empty

Key insight: Once a node's shortest distance is finalized, it won't be updated again because all edge weights are non-negative.

Time and Space Complexity

Implementation Time Complexity Description
Array Implementation O(V²) Linear search for minimum each time
Binary Heap O((V+E)log V) Common implementation
Fibonacci Heap O(E + V log V) Theoretical best, complex implementation
Space Complexity O(V) Store distances and priority queue

Note: Dijkstra cannot handle negative edge weights. Use Bellman-Ford for graphs with negative edges.

Applications

  • GPS navigation shortest route planning
  • Network routing protocols (OSPF, IS-IS)
  • Shortest relationship chain in social networks
  • NPC pathfinding in games
  • Flight/railway optimal route queries
Navigation Network Routing Game Dev Path Planning

Implementation

import heapq

def dijkstra(graph, start):
    """Dijkstra最短路径算法
    graph: 邻接表 {node: [(neighbor, weight), ...]}
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}
    
    # 优先队列: (距离, 节点)
    pq = [(0, start)]
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        # 跳过已处理的节点
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current
                heapq.heappush(pq, (distance, neighbor))
    
    return distances, previous


# 使用示例
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}
dist, prev = dijkstra(graph, 'A')
print(dist)  # {'A': 0, 'B': 3, 'C': 2, 'D': 8}
import java.util.*;

public class Dijkstra {
    
    public static Map<String, Integer> dijkstra(
            Map<String, List<int[]>> graph, 
            String start) {
        
        Map<String, Integer> distances = new HashMap<>();
        for (String node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        
        // 优先队列: [距离, 节点索引]
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
        pq.offer(new int[]{0, start.hashCode()});
        
        Set<String> visited = new HashSet<>();
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currDist = curr[0];
            
            // 找到对应节点
            String currNode = null;
            for (String n : graph.keySet()) {
                if (n.hashCode() == curr[1]) {
                    currNode = n;
                    break;
                }
            }
            
            if (visited.contains(currNode)) continue;
            visited.add(currNode);
            
            for (int[] edge : graph.get(currNode)) {
                // edge[0] = neighbor index, edge[1] = weight
                int newDist = currDist + edge[1];
                // 更新距离并加入队列...
            }
        }
        
        return distances;
    }
}