Dijsktra最短路径算法

本文主要是介绍Dijsktra最短路径算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dijsktra最短路径算法是一种贪心算法。从图中某个起点开始向外逐步扩张，得到到达所有点的最短路径（如果有目标终点那么可以提前结束）。

算法步骤：

1 初始化一个open表和一个closed表，open表中存放顶点和此点到起点的距离，closed表中存放已找到最短路径的顶点

2 将起点加入open表，其到起点的距离为0

3 从open表中拿出一个到起点距离最小的顶点v，其到起点的距离为d，如果open表是空的则结束

4 如果closed表中存在顶点v，则回到步骤3

5 将v加入closed表

6 对于从顶点v出发能直接到达的每一个不在closed表中的顶点，加入open表中，其到起点的距离为d + (v到此点的边的距离)

7 回到步骤3

根据以上步骤，由于open表需要快速找到最小的元素，因此适合用优先队列实现；由于closed表需要快速找到元素是否存在表中，因此适合用哈希表实现。

java代码实现：

import java.util.Arrays;
import java.util.PriorityQueue;public class Dijsktra {private static class Vertex implements Comparable<Vertex> {public final int index;public final int length;public Vertex(int index, int length) {this.index = in

这篇关于Dijsktra最短路径算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---