Dijkstra Algorithm Java

Dijkstra 算法是一种寻找源节点到目标节点最短路径的著名算法。它采用贪心方法来寻找最短路径。Dijkstra 算法的概念是从源点开始找到最短距离（路径），并在更新时忽略较长的距离。

在本节中，我们将用 Java 程序实现 Dijkstra 算法。我们还将讨论它的用法和局限性。

Dijkstra 算法步骤

步骤 1：所有节点应标记为未访问。

步骤 2：所有节点必须初始化为“无限”（一个大数）距离。起始节点必须初始化为零。

步骤 3：将起始节点标记为当前节点。

步骤 4：从当前节点开始，分析所有尚未访问的邻居，并通过将连接当前节点和邻居节点的边的权重加到当前节点的当前距离来计算它们的距离。

步骤 5：现在，将最近计算的距离与分配给邻居节点的距离进行比较，并将其视为邻居节点的当前距离。

步骤 6：之后，考虑当前节点周围尚未访问的邻居，并将当前节点标记为已访问。

步骤 7：当结束节点被标记为已访问时，算法就完成了；否则，

步骤 8：选择已分配最小距离的未访问节点，并将其视为新的当前节点。之后，从步骤 4 开始。

Dijkstra 算法伪代码

Dijkstra 算法实现

以下代码使用下面提到的图实现了 Dijkstra 算法。

文件名：DijkstraExample.java

输出

The shortest Distance from source 0th node to all other nodes are: 
To 0 the shortest distance is: 0
To 1 the shortest distance is: 3
To 2 the shortest distance is: 8
To 3 the shortest distance is: 10
To 4 the shortest distance is: 18
To 5 the shortest distance is: 10
To 6 the shortest distance is: 9
To 7 the shortest distance is: 7
To 8 the shortest distance is: 7

上述代码的时间复杂度为 O(V^2)，其中 V 是图中顶点的总数。这种时间复杂度在图较小时影响不大，但在图较大时会带来很大麻烦。因此，我们需要进行优化以降低这种复杂度。借助优先队列，我们可以降低时间复杂度。观察为上述图编写的代码。

文件名：DijkstraExample1.java

输出

The shortest path from the node:
0 to 0 is 0
0 to 1 is 3
0 to 2 is 8
0 to 3 is 10
0 to 4 is 18
0 to 5 is 10
0 to 6 is 9
0 to 7 is 7
0 to 8 is 7

上述实现的 time complexity 为 O(V + E*log(V))，其中 V 是顶点的总数，E 是图中的边数。

Dijkstra 算法的局限性

以下是 Dijkstra 算法的一些局限性：

1. 当边具有负值时，Dijkstra 算法不起作用。
2. 对于有环图，该算法无法评估最短路径。因此，对于有环图，不建议使用 Dijkstra 算法。

Dijkstra 算法的用法

Dijkstra 算法的一些突出用途是：

1. Google 地图使用此算法。
2. 该算法用于查找两个地点之间的距离。
3. 在 IP 路由中，该算法也用于发现最短路径。