迪杰斯特拉算法java实现

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找图中两个节点之间最短路径的贪心算法。在Java中实现迪杰斯特拉算法通常会涉及以下几个步骤：

1. 定义数据结构：首先需要一个优先队列（通常使用`PriorityQueue`，可以自定义比较规则）存储边权重和邻居节点，以及一个邻接矩阵或邻接表来表示图。

import java.util.*;

class Node {
    int id;
    double distanceFromStart;
    boolean isVisited;

    // getters and setters
}

2. 初始化：将起始节点的距离设为0，其他所有节点的距离设为无穷大，标记未访问。

3. 主循环：从优先队列中取出当前距离最小的节点，然后更新其相邻节点的距离，并在已知更优路径的情况下更新它们。

List<Node> nodes = ...; // 图中所有节点
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingDouble(Node::distanceFromStart));

queue.offer(new Node(startId, 0.0, false));
while (!queue.isEmpty()) {
    Node currentNode = queue.poll();
    if (currentNode.isVisited) continue;
    currentNode.isVisited = true;
    
    for (Node neighbor : neighbors[currentNode.id]) {
        double tentativeDistance = currentNode.distanceFromStart + neighbor.getWeight(); 
        if (tentativeDistance < neighbor.distanceFromStart && !neighbor.isVisited) {
            neighbor.distanceFromStart = tentativeDistance;
            neighbor.parent = currentNode; // 记录父节点
            queue.offer(neighbor);
        }
    }
}

4. 检查并返回结果：遍历每个节点，通过回溯找到最短路径。从目标节点开始，沿着parent指针一直向上追溯到起始节点，记录路径。