图论之最短路径（Bellman-Ford算法、Dijkstra算法、SPFA算法、Floyd-Warshall算法实现）
前言：
前几天考研复习了图论算法，现在抽点时间，写下博客记录下。
最短路径的定义：
给定图G(V,E)，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。
常用的最短路算法有：Bellman-Ford算法、Dijkstra算法、SPFA算法、Floyd-Warshall算法。
Bellman-Ford算法：
Bellman-Ford算法以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。此算法在计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。Bellman-Ford算法 简单地对所有边进行松弛操作，共 V-1 次，其中 V 是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。Bellman-Ford算法适用于边权为负数的情况。
Bellman-Ford 的时间复杂度为：O(V∗E)O(V*E)O(V∗E)（V为图的顶点数、E为图的边数）。
代码如下：
//edges为无向图，边（起点、终点、权值），dist为源点s出发的最短路径值数组
void bellman_ford(int s)
{
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
//由于最短路不会经过同一顶点两次，所以最短路最多有n-1条边，因此有些时候可以利用这个性质检查图是否存在负圈
for (int j = 0; j < n - 1; ++j)
{
for (int i = 0; i dist[a] + w)
{
dist[b] = dist[a] + w;
}
}
}
}
Dijkstra算法：
Dijkstra算法基于贪心，贪心算法中最重要的一部分就是贪心策略，在这个算法中，贪心策略就是，去寻找点i，满足min(d[i]) i∈ B，满足这个条件的点 i，必定是无法被继续松弛的点，如果说要松弛点 i，那么必定通过 A 中或者 B 中的点进行更新，若通过 B 中的点j进行更新那么松弛之后的路径为d[j] + a[j][i]。由于 d[i] 已经是最小了，因此d[j]+a[j][i]>d[i] 因此不可能是通过 B 中的点进行松弛，若通过 A 中的点 m 进行松弛，由于 m 是点集A中的点，因此点 m 一定松弛过点i，重复的松弛没有意义的。因此，我们找到的点i，现在的d[i]，一定是从源点到点 i 路径最小的点了。
Dijkstra+heap 优化的时间复杂度为：O((V+E)logV)O((V+E)logV)O((V+E)logV)。
void dijkstra(int s)
{
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
//pair的first表示最短路径，second表示源点s
priority_queue<pair, vector<pair>, greater<pair>> q; //小根堆
q.push(make_pair(0, s));
while (!q.empty())
{
pair p = q.top();
q.pop();
int v = p.second;
if (dist[v] dist[v] + edge.second)
{
dist[edge.first] = dist[v] + edge.second;
q.push(make_pair(dist[edge.first], edge.first));
}
}
}
}
SPAF算法：
SPFA即 Bellman-ford队列优化算法，代码实现与 Dijkstra 类似，二者都是用于求单源最短路径的算法。区别在于SPFA可以检测负权环：
利用 spfa 算法判断负环有两种方法：
1） spfa 的 dfs 形式，判断条件是存在一点在一条路径上出现多次。 2） spfa 的 bfs 形式，判断条件是存在一点入队次数大于总顶点数。总的应用场景上：
如果是稠密图，Dijkstra+heap 比 SPFA 快，稀疏图则是 SPFA 比较快 如果求最短路径，则 SPFA+BFS 比较快，如果是负环检测，则是 SPFA+DFS 比较快。SPFA+BFS 时间复杂度为O(V∗E)O(V*E)O(V∗E)。
//从源点s出发建立最短路径
void SPFA(int s) {
queue q;
bool inq[maxn] = {false};
for(int i = 1; i dis[x] + e[i].w) {
dis[k] = dis[x] + e[i].w;
if(!inq[k]) {
inq[k] = true;
q.push(k);
}
}
}
}
}
Floyd-Warshall算法：
Floyd-Warshall算法是求任意两点之间的最短路。此算法基于的事实是：如果存在顶点 k，使得以 k 作为中介点的顶点 i、j 的当前距离是缩短，即dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
Floyd-Warshall算法的时间复杂度时间复杂度为O(n∗n∗n)O(n*n*n)O(n∗n∗n)。
void Floyd_Warshall(vector<vector>& edges)
{
//1、建立并初始化dp数组，若(i,j)之间存在边，dp[i][j]则为边ij的权值，否则为0x3f3f3f3f
int dp[n][n];
memset(dp, 0x3f, sizeof(dp));
for (const auto &edge : edges)
{
dp[edge[0]][edge[1]] = dp[edge[1]][edge[0]] = edge[2];
}
//2、开始进行floyd算法求dp数组
for (int k = 0; k < n; ++k)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
作者：algsup
