Dijkstra算法（模板）

### Dijkstra算法模板代码实现

#### Java版本示例
Dijkstra算法用于解决单源最短路径问题，即给定图中的一个起点，求解此点到其余各顶点的最短路径。下面展示了一个基于优先队列优化版的Dijkstra算法Java实现[^1]。

import java.util.*;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;

    public static Map<Integer, Integer> dijkstra(Map<Integer, List<int[]>> graph, int start) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        Map<Integer, Integer> distTo = new HashMap<>();
        
        for (int node : graph.keySet()) {
            distTo.put(node, INF);
        }
        distTo.put(start, 0);

        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0];
            int d = curr[1];

            if (d > distTo.get(u)) continue;
            
            for (int[] neighbor : graph.getOrDefault(u, Collections.emptyList())) {
                int v = neighbor[0], weight = neighbor[1];
                
                if (distTo.get(u) + weight < distTo.get(v)) {
                    distTo.put(v, distTo.get(u) + weight);
                    pq.offer(new int[]{v, distTo.get(v)});
                }
            }
        }

        return distTo;
    }
}

这段代码定义了`dijkstra`方法接收邻接表形式存储的无向加权图以及起始节点作为参数，并返回从起始节点出发到达各个节点所需的最小距离映射表。

对于更具体的场景需求——例如获取指定两点间的最短路径而非所有可达点的距离，则可以参照另一种思路，在遍历过程中维护前驱指针以便后续回溯构建具体路径[^2]。

#### C# 版本示例
当仅需关注特定两节点间最短路径时，可采用如下方式：

using System.Collections.Generic;

public class Node {
    public string Name { get; set; }
    public Dictionary<Node, double> Edges { get; set; } = new Dictionary<Node, double>();
}

public static List<Node> GetShortestPath(Node start, Node end) {
    var distances = new Dictionary<Node, double>();
    foreach(var n in start.Graph.Nodes){
        distances[n]=double.PositiveInfinity;
    }
    
    distances[start] = 0;
    var previousNodes = new Dictionary<Node, Node>();

    var unvisited = new HashSet<Node>(start.Graph.Nodes);

    while(unvisited.Count > 0 && !unvisited.Contains(end)){
        // Select the unvisited vertex with smallest known distance from source.
        var currentMinDistanceVertex = unvisited.MinBy(n => distances[n]);
        unvisited.Remove(currentMinDistanceVertex);

        foreach (var edge in currentMinDistanceVertex.Edges.Keys) {
            if(!unvisited.Contains(edge))
               continue;
               
            var altDist = distances[currentMinDistanceVertex]+currentMinDistanceVertex.Edges[edge];
            if(altDist<distances[edge]){
                distances[edge]=altDist;
                previousNodes[edge]=currentMinDistanceVertex;
            }
        }
    }

    var path = new Stack<Node>();
    for (Node node = end; node != null; node = previousNodes.GetValueOrDefault(node))
        path.Push(node);

    return new List<Node>(path);
}

在此段C#代码中，通过引入字典`previousNodes`保存每个访问过的节点及其对应的上一跳节点信息，从而能够在完成整个图结构上的松弛操作之后逆序重构出完整的最短路径列表。