Java中的Dijkstra算法实现

1. 概述

本文重点讨论图论中的经典问题——最短路径问题（SPP），以及如何使用 Dijkstra算法 解决它。该算法的核心目标是：在带权图中，从指定起点出发，计算到所有其他节点的最短路径。

2. Dijkstra算法解决最短路径问题

给定一个正权图和起点（节点A），Dijkstra算法能确定起点到图中所有目标节点的最短路径和距离：

step1

算法的核心思想是：持续淘汰起点到各目标节点的较长路径。为跟踪处理过程，需维护两个节点集合：

已确定节点集：已知从起点到该节点的最短距离
待处理节点集：可从起点到达但尚未确定最短距离的节点

以下是算法步骤：

起点距离设为0
其他节点距离设为无穷大（Integer.MAX_VALUE）
将起点加入待处理节点集
当待处理节点集非空时：
- 从待处理集中选择距离起点最近的节点作为当前评估节点
- 计算当前节点到其直接邻居的新距离，保留最小值
- 将未确定的邻居节点加入待处理集

这些步骤可分为初始化和评估两个阶段。下面结合示例图说明：

2.1 初始化阶段

开始探索前，需初始化所有节点：

起点（A）距离设为0
其他节点距离设为无穷大，前驱节点设为未知

初始化后的节点状态如下：

step1

最后将起点A加入待处理节点集（此时已确定节点集为空）。

2.2 评估阶段

从待处理集中选择距离最小的节点（初始为A），评估其未确定的邻居：

step2

核心操作：将当前节点距离与边权相加，与目标节点距离比较。例如：

节点B：0+10 < ∞ → 更新距离为10，前驱设为A
节点C：0+15 < ∞ → 更新距离为15，前驱设为A

然后将A移入已确定集，B、C加入待处理集。重复此过程直到所有节点被确定：

step8

以下是完整的评估过程迭代表：

迭代	待处理集	已确定集	评估节点	B	C	D	E	F
1	A	–	A	A-10	A-15	X-∞	X-∞	X-∞
2	B, C	A	B	A-10	A-15	B-22	X-∞	B-25
3	C, F, D	A, B	C	A-10	A-15	B-22	C-25	B-25
4	D, E, F	A, B, C	D	A-10	A-15	B-22	D-24	D-23
5	E, F	A, B, C, D	F	A-10	A-15	B-22	D-24	D-23
6	E	A, B, C, D, F	E	A-10	A-15	B-22	D-24	D-23
最终	–	ALL	NONE	A-10	A-15	B-22	D-24	D-23

符号说明：B-22表示节点B是前驱节点，总距离为22

最终从起点A出发的最短路径：

✅ 节点B：A → B（距离10）
✅ 节点C：A → C（距离15）
✅ 节点D：A → B → D（距离22）
✅ 节点E：A → B → D → E（距离24）
✅ 节点F：A → B → D → F（距离23）

3. Java实现

3.1 图结构定义

用Graph类表示图，包含节点集合：

public class Graph {
    private Set<Node> nodes = new HashSet<>();
    
    public void addNode(Node node) {
        nodes.add(node);
    }
    // getters and setters
}

Node类包含：

节点名称
最短路径（链表）
到起点的距离
邻接节点映射（存储邻居节点及边权）

public class Node {
    private String name;
    private List<Node> shortestPath = new LinkedList<>();
    private Integer distance = Integer.MAX_VALUE;
    private Map<Node, Integer> adjacentNodes = new HashMap<>();

    public void addDestination(Node destination, int distance) {
        adjacentNodes.put(destination, distance);
    }
 
    public Node(String name) {
        this.name = name;
    }
    // getters and setters
}

⚠️ adjacentNodes使用邻接表实现，比邻接矩阵更适合Dijkstra算法

3.2 算法实现

核心算法实现：

public static Graph calculateShortestPathFromSource(Graph graph, Node source) {
    source.setDistance(0);

    Set<Node> settledNodes = new HashSet<>();
    Set<Node> unsettledNodes = new HashSet<>();
    unsettledNodes.add(source);

    while (!unsettledNodes.isEmpty()) {
        Node currentNode = getLowestDistanceNode(unsettledNodes);
        unsettledNodes.remove(currentNode);
        
        for (Map.Entry<Node, Integer> adjacencyPair : 
             currentNode.getAdjacentNodes().entrySet()) {
            Node adjacentNode = adjacencyPair.getKey();
            Integer edgeWeight = adjacencyPair.getValue();
            
            if (!settledNodes.contains(adjacentNode)) {
                calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
                unsettledNodes.add(adjacentNode);
            }
        }
        settledNodes.add(currentNode);
    }
    return graph;
}

辅助方法：

getLowestDistanceNode()：从待处理集中选择距离最小的节点
calculateMinimumDistance()：更新最短距离和路径

private static void calculateMinimumDistance(Node evaluationNode, 
                                           Integer edgeWeight, 
                                           Node sourceNode) {
    Integer sourceDistance = sourceNode.getDistance();
    if (sourceDistance + edgeWeight < evaluationNode.getDistance()) {
        evaluationNode.setDistance(sourceDistance + edgeWeight);
        LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());
        shortestPath.add(sourceNode);
        evaluationNode.setShortestPath(shortestPath);
    }
}

3.3 使用示例

构建示例图并计算最短路径：

Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");

nodeA.addDestination(nodeB, 10);
nodeA.addDestination(nodeC, 15);

nodeB.addDestination(nodeD, 12);
nodeB.addDestination(nodeF, 15);

nodeC.addDestination(nodeE, 10);

nodeD.addDestination(nodeE, 2);
nodeD.addDestination(nodeF, 1);

nodeF.addDestination(nodeE, 5);

Graph graph = new Graph();
graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);
graph.addNode(nodeE);
graph.addNode(nodeF);

graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA);

执行后，每个节点的shortestPath和distance属性将被更新，结果与第2节的理论计算完全一致

4. 总结

本文详细介绍了Dijkstra算法如何解决最短路径问题，并给出了完整的Java实现。核心要点：

✅ 适用于正权图的最短路径计算
✅ 通过维护两个节点集（已确定/待处理）逐步求解
✅ 时间复杂度为O(V²)（V为节点数），可用优先队列优化至O(E+V log V）

完整实现代码可在 GitHub项目中获取。

Persistence

REST

Security