最短路径问题-Dijkstra算法(Java)

最短路径问题是指在一个加权图中找到从起点到其他所有顶点的最短路径问题。Dijkstra算法是一种高效的求解这个问题的方法，它适用于边是有向或无向的，并且边的权重都是非负的。

以下是使用Java实现Dijkstra算法的基本步骤：

1. 初始化：创建一个优先队列（通常用`PriorityQueue`），将起点的距离设为0，其余节点距离设为无穷大。同时，标记所有节点为未访问。

2. 主循环：每次从未访问过的节点中取出当前距离起点最近的一个（即最小值）。然后更新该节点的所有邻居，如果通过邻居到达比当前已知更短的距离，则更新邻居的距离并标记其为已访问。

3. 更新邻接节点：对于每一个相邻节点，计算从起点到它的新距离（旧距离加上从起点到这个节点的边的权重），如果这个新的总距离小于之前存储的距离，就更新该节点的距离。

4. 结束条件：当队列为空，或者当前节点是目标节点时，算法结束。这时，从起点到目标节点的最短路径已经被找到。

import java.util.*;

public class Dijkstra {
    private int[][] graph;
    private int[] dist;

    public List<int[]> dijkstra(int src, int V) {
        // ... (这里省略了具体实现细节)
        // 回调函数、数组初始化等部分
        return shortestPaths;
    }
}