一、最短路算法

1. 朴素Dijkstra算法

Dijkstra算法用来求所有边权都是正数的单源最短路。边权即两个点之间的距离；单源, 即只求从源点（起点，终点也称为汇点）到其他点的最短距离；

朴素Dijkstra 算法适用于求稠密图的最短距离问题。稠密图是指边数有很多的图，假设 n 为图的点数， m 为图的边数，那么一般当 m = n²时该图为稠密图。朴素Dijkstra算法的时间复杂度为 O(n²)。该算法基于贪心算法。

算法流程如下：

1. 使用一个 dist[] 数组用来存储从源点到其它点的距离。初始化 dist[1] = 0 ，其它点的 dist 值为正无穷大（可以使用一个很大的数来表示，比如 0x3f3f3f3f)。
2. 找到一个尚未确定并且距离起点距离最近的点 t。然后标记该节点。
3. 扫描节点 t 的所有出边（t -> j)，如果源点到 j 的距离比源点到 t 再从 t 到 j 的距离 g[t][j] 之和大，那么就使 dist[j] = dist[t] + g[t][j]。
4. 重复步骤 2 和 3 直到所有的点都被标记。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：多目标遗传算法NSGA-II原理详解及算法实现

下一篇：Linux自动化交互命令expect测试

【算法基础】最短路算法（朴素Dijkstra + 堆优化Dijkstra + Bellman-Ford +SPFA + Floyd）

一、最短路算法

1. 朴素Dijkstra算法

算法流程如下：

相关内容

热门资讯