最短路径#

定义：从一个顶点 v0 到图中任意一个顶点 v1 的路径长度最小的路径。

BFS算法#

同树，森林的BFS算法。

因为BFS总是按照距离由近到远的顺序遍历图中的顶点，从而保证每个顶点首次被访问时，所经过的路径为最短路径

Eg：适合无权图

Dijkstra算法#

算法原理：

Dijkstra算法使用一个集合S记录已经确定最短路径的顶点。

tep1：将源点 a 放入S，并存储最短路径 {a,b} 。

tep2：将新顶点 b 加入 S 后，并存储最短路径 {a,b,c} 。

tep3：直到所有顶点都加入 S 中 。

Eg：求单源最短路径

Dijkstra动画演示#

Floyd算法#

Floyd算法使用邻接矩阵存储图

算法原理简单来说：

依次将每个点做为 “中间点” 去更新。

Path 存储的是终点的前一个结点，便于查找路径。

图示 分别是 初始 $D^{-1}$ 和 以 0 作为中间点 $D^0$ 更新 。

直到更新到最后一个顶点。

Eg：求各顶点之间的最短路径

Floyd动画演示#

BFS,Dijkstra,Floyd总结#