Dijkstra最短路径可视化 - 图算法动画

Dijkstra算法用于在带权图中找到从源点到所有其他顶点的最短路径。它采用贪心策略，每次选择当前距离最小的未访问顶点进行扩展。

算法步骤

初始化：源点距离设为0，其他所有节点距离设为无穷大
将源点加入优先队列（最小堆）
取出队列中距离最小的节点u
对于u的每个邻居v，如果通过u到达v的距离更短，则更新v的距离
将更新后的邻居加入优先队列
重复步骤3-5直到队列为空

关键洞察：已确定最短距离的节点不会再被更新，因为所有边权重非负。

时间与空间复杂度

实现方式	时间复杂度	说明
数组实现	O(V²)	每次线性查找最小值
二叉堆	O((V+E)log V)	常用实现方式
斐波那契堆	O(E + V log V)	理论最优但实现复杂
空间复杂度	O(V)	存储距离和优先队列

注意：Dijkstra不能处理负权边。对于负权图，应使用Bellman-Ford算法。

应用场景

GPS导航系统的最短路线规划
网络路由协议（OSPF、IS-IS）
社交网络中的最短关系链
游戏中的NPC寻路
航班/铁路最优路线查询

导航系统网络路由游戏开发路径规划

代码实现

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;
    }
}