Dijkstra算法在Java中的实现43

Dijkstra算法是一种贪心算法，用于求一个加权图中从一个顶点到其他所有顶点的最短路径。该算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。本文将介绍Dijkstra算法在Java中的实现，并讨论其时间复杂度和应用场景。

算法描述

Dijkstra算法使用一个优先队列来跟踪未访问的顶点及其到初始顶点的当前估计最短路径权重。算法的步骤如下：
初始化：将起始顶点添加到优先队列，其权重为0。将所有其他顶点的权重初始化为无穷大。
循环：当优先队列不为空时，执行以下步骤：

从优先队列中删除权重最小的顶点。
将该顶点标记为已访问。
检查该顶点的相邻顶点。对于每个相邻顶点：

如果相邻顶点未被访问，则将相邻顶点的权重更新为当前顶点的权重加上当前顶点到相邻顶点的边权重，如果更新后的权重比以前的小。
将相邻顶点添加到优先队列。

结束：当优先队列为空时，算法结束。每个顶点的权重现在表示从起始顶点到该顶点的最短路径权重。

Java实现

以下Java代码展示了Dijkstra算法的一种实现：```java
import .*;
public class Dijkstra {
// 表示图中顶点的类
private static class Vertex {
private int id; // 顶点编号
private int weight; // 到初始顶点的最短路径权重
private List edges; // 从该顶点出发的边
public Vertex(int id) {
= id;
= Integer.MAX_VALUE; // 初始化权重为无穷大
= new ArrayList();
}
}
// 表示图中边的类
private static class Edge {
private Vertex to; // 目标顶点
private int weight; // 边权重
public Edge(Vertex to, int weight) {
= to;
= weight;
}
}
// 求图中从给定顶点到其他所有顶点的最短路径
public static Map dijkstra(Graph graph, Vertex start) {
// 初始化优先队列，以权重为排序键
PriorityQueue pq = new PriorityQueue((Vertex::getWeight));
// 初始化顶点信息
for (Vertex vertex : ()) {
(vertex);
}
(0);
// 存储结果
Map distances = new HashMap();
while (!()) {
// 取出权重最小的顶点
Vertex v = ();
// 存储结果
(v, ());
// 遍历该顶点的相邻顶点
for (Edge edge : ()) {
Vertex w = ();
// 如果相邻顶点未被访问
if (!()) {
// 更新相邻顶点的权重
if (() + () < ()) {
(() + ());
(w);
}
}
}
}
return distances;
}
public static void main(String[] args) {
// 创建一个图
Graph graph = new Graph();
// 添加顶点
Vertex v1 = (1);
Vertex v2 = (2);
Vertex v3 = (3);
Vertex v4 = (4);
Vertex v5 = (5);
// 添加边
(v1, v2, 1);
(v1, v3, 2);
(v2, v4, 3);
(v3, v4, 4);
(v4, v5, 5);
// 计算最短路径
Map distances = dijkstra(graph, v1);
// 打印结果
for (Vertex vertex : ()) {
(("最短路径（起点：%d，终点：%d）：%d",
(), (), (vertex)));
}
}
}
```