ps:给17级讲最短路径时候自己写的课件
目录
最短路径... 1
概述: 1
Floyd算法（弗洛伊德算法）复杂度O(n^3) 3
Dijkstra算法（迪杰斯特拉算法）复杂度O(nlog2n) 5
SPFA算法(Shortest Path Fast Algorithm的缩写) 12
附录：... 12
Floyd代码... 12
Dijkstra O(n^2),链式前向星... 13
Dijkstra + priority_queue + 链式前向星... 15
最短路径 概述:假设有一个图，点表示城市，边表示路径长度。
如图，从点(2)到点(4)有若干总走法，比如
(2)->(3)->(4), 这么走路径长度是4。
也可以(2)->(3)->(1)->(4) 这样路径长度是15。当图有上万个点的时候就无法用人工直接求任意两点的路径，哪一条是最短的。最短路径就是解决这类问题。
例题：?pid=1499
Floyd算法（弗洛伊德算法）复杂度O(n^3)const int inf = 0x3f3f3f3f;
由于某些情况下避免正无穷加正无穷加成负无穷，所以正无穷有时不用0x7FFFFFFF, 用0x3f3f3f3f,或者1<<29, 1e9.
这个算法只能用邻接矩阵存图， 我们先初始化一下矩阵
void init() { ///初始化矩阵
for(int i = 1; i <= n; i ++ ) {
for(int j = 1; j <= n; j ++ ) {
if(i == j) {
mp[i][j] = 0; ///自己到自己的距离0
} else {
mp[i][j] = inf;///否则都是inf
}
}
}
}
然后读入一条u->v权值为w的边。对于矩阵mp[u][v]记录的是u->v的边的长度。对于无向图，mp[u][v]和mp[v][u]是相等的。而因为我们求的是最短路, u->v的路有多条我们只要存最短的。
scanf("%d %d %d", &u, &v, &w);
mp[u][v] = mp[v][u] = min(mp[u][v], w);
存好矩阵后我们跑floyd算法，核心代码就这几行
for(int k = 0; k < n; k ++ ) {
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < n; j ++ ) {
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
}
}
然后矩阵mp[s][t]的值就是s->t的最短路径。对于这题来说就是
printf("%d\n", mp[s][t] == inf ? -1 : mp[s][t]);
下面我们来解释一下floyd的三层循环。
我们发现(i)->(j)的最短路径可能是之间i->j,也可能是经过中间点i->k->j。
如果我们用dp[i][j]表示u->v的最短路径。那么
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
然后看循环。
当k = 0时
枚举I,j.我们尝试让编号0的中点。优化我们的最短距离。
矩阵成为了经过0点优化过的最短距离。
K = 1时，我们又枚举I,j。让矩阵成为经过中间点0,1的最短路矩阵。
以此类推
。。。。
来自知乎的解释
优点:好写，核心代码总共就4行。经常扩展出各种图上动态规划
缺点:复杂度高。点的数量1000的图就容易TLE
Dijkstra算法（迪杰斯特拉算法）复杂度O(nlog2n)我们先有张图，我们要求1->5的最短路径是什么。
换个问题，我们要求一个dist数组，dist[i]表示起点到i的最短路径。
如果起点是1，初始化dist[1] = 0,其余都是正无穷
我们的dist[]数组已经完成了dist[1](蓝色)，和1相连的有两条边。