本文为图论的学习总结，讲解最短路径算法。

当边的权值全相同时，我们可以从起点出发对图进行 BFS，遇到终点时停止。由此得到的广度优先生成树上，从根节点到终点节点就是中转次数（即总权值）最少的路径。

但实际情况中，边的权值不完全相同，我们通常这个问题分为两类，一种是从某个源点到其余各顶点的最短路径（单源），另一种是每一对顶点间的最短路径（多源）。

单源

迪杰斯特拉

首先将起点放入集合 $S$S，对其余各点标记起点到该点的最小距离和路径。找一条从 $S$S 中出去的最短边加入边集 $E$E，将边的终点加入 $S$S，并更新各点标记。不断重复直到所有点都被标记。

编程实现见【Dijkstra 算法】，算法复杂度为 $O(n^2)$O(n2)。

其他算法

其他算法如 Bellman Ford、SPFA、堆优化的 Dijkstra 等见【单源最短路径】、【A* 算法】、【模拟退火算法】、【遗传算法】。

多源

弗洛伊德

如果将 Dijkstra 算法重复 $n$n 次也可以进行求解，Floyd 算法形式上更加简单。

若 $(v_i,…,v_k)$(vi​,…,vk​) 和 $(v_k,…,v_j)$(vk​,…,vj​) 分别是从 $v_i$vi​ 到 $v_k$vk​ 和从 $v_k$vk​ 到 $v_j$vj​ 的中间顶点序号不大于 $k-1$k−1 的最短路径，则将 $(v_i,…,v_k,…,v_j)$(vi​,…,vk​,…,vj​) 和已经得到的从 $v_i$vi​ 到 $v_j$vj​ 且中间顶点序号不大于 $k-1$k−1 的最短路径相比较，较短者就是从 $v_i$vi​ 到 $v_j$vj​ 的中间顶点序号不大于 $k$k 的最短路径。经过 $k$k 次比较后，最后求得的必是 $v_i$vi​ 到 $v_j$vj​ 的最短路径。

编程实现见【Floyd 算法】，算法复杂度为 $O(n^3)$O(n3)。

旅行商问题

见【哈密顿回路】。

有帮助的话点个赞加关注吧