1.单元最短路径
注：带权路径长度——当图是带权图时，一条路径上所有的权值之和，称为该路径的带权路径长度
1.BFS算法（无权图）
BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图。
2.Dijkstra算法
- 1.初始：选择从任意一个顶点开始，初始化三个数组信息如下。
1.标记各顶点是否已找到最短路径，记数组final[10]
2.记录最短路径长度数组为dist[10]
3.记录当前路径上的前驱数组为path[10]
2.循环遍历所有结点，找到还没有确定最短路径，且dist最小的顶点Vi，令final[i]=是。
检查所有邻接自Vi的顶点，若其final值为否，则更新dist和path数组。3.循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点Vi，令final[i]=是。
检查所有邻接自Vi4.结论
Dijkstra算法不适于有负权值的带权图。
3.Floyd算法
问题：求出每一对顶点之间的最短路径
解决：使用动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意一对顶点Vi->Vj之间的最短路径可分为如下几个阶段:
- 1.初始：不允许在其他顶点中转，最短路径是？
- 2.第1步：若允许在V0中转，最短路径是？
- 3.第2步：若允许在V0，V1中转，最短路径是？
- 4.第3步：若允许在V0，V1，V2中转，最短路径是？
- 5，6,7........
- n.第(n-1)步：若允许在V0，V1，V2，....V(n-1)中转，最短路径是？
代码实现
// 主要实现，side数组存储的是各顶点之间的边
for(int k=0; k<n; k++){ // 动态的考虑以某个顶点为中转点
for(int i=0; i<n; i++){ // 遍历整个矩阵，i为行号，j为列号
for(int k=0; j<n; j++){
if(side[i][j] > side[i][k] + side[k][j]){ // 以当前顶点为中转点的路径更短
side[i][j] = side[i][k] + side[k][j]; // 更新最短路径长度
path[i][j] = k; // 中转点
}
}
}
}
结论
可以解决负权值的带权图，但是不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径。
4.3种最短路径算法总结
| BFS算法 | Dijkstra算法 | Floyd算法 | |
|---|---|---|---|
| 无权图 | 是 | 是 | 是 |
| 带权图 | 否 | 是 | 是 |
| 带负权值的图 | 否 | 否 | 是 |
| 带负权回路的图 | 否 | 否 | 否 |
| 时间复杂度 | O([V]^2)或者O([V]+[E]) | O([V]^2) | O([V]^3) |
| 通常用于 | 求无权图的单源最短路径 | 求带权图的单源最短路径 | 求带权图中各顶点间的最短路径 |
