这里主要介绍Floyd算法、Dijkstra算法和SPFA算法,由于Bellman-ford算法可优化为SPFA,故暂时忽略它。
适用范围:无负权回路,边权可正负。
核心代码:
for (k = 1; k <= n; k++) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; path[i][j] = path[i][k]; } }
时间复杂度:\(O(n^3)\)
优势:代码简单,用于稠密图效果更佳,求出所有点两两之间最短路。
缺点:时间复杂度较高。
适用范围:不存在负权边,求单源最短路。
核心代码:
void Dijkstra(int u) { memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) { dis[i] = map[u][i]; //初始化 } vis[u] = 1; for (int t = 1; t < n; t++) { int minn = Inf, temp; for (int i = 1; i <= n; i++) { if (!vis[i] && dis[i] < minn) { minn = dis[i]; temp = i; } } vis[temp] = 1; for (int i = 1; i <= n; i++) { if (map[temp][i] + dis[temp] < dis[i]) { dis[i] = map[temp][i] + dis[temp]; } } } }
可加入堆优化:
#include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; struct node { int di; int xu; bool operator<(const node &rhs) const { return di > rhs.di; } }; struct edge { int to, nxt, v; } e[200001]; int n, m, s; int num_edge = 0, head[100001]; int dis[100001], v[100001]; priority_queue<node> Q; void add(int pre, int to, int vi) { e[++num_edge].nxt = head[pre]; e[num_edge].to = to; e[num_edge].v = vi; head[pre] = num_edge; } int main() { memset(dis, 0x3f, sizeof(dis)); scanf("%d%d%d", &n, &m, &s); for (int i = 1; i <= m; i++) { int ui, vi, wi; scanf("%d%d%d", &ui, &vi, &wi); add(ui, vi, wi); } dis[s] = 0; node oop = {dis[s], s}; Q.push(oop); while (!Q.empty()) { node now = Q.top(); Q.pop(); int u = now.xu; if (vis[u] == 1) continue; //关键 vis[u] = 1; for (int i = head[u]; i; i = e[i].nxt) { int gt = e[i].to, jz = e[i].v; if (dis[u] + jz < dis[gt]) { dis[gt] = dis[u] + jz; node xt = {dis[gt], gt}; Q.push(xt); } } } for (int i = 1; i <= n; i++) { cout << dis[i] << " "; } }
时间复杂度:\(O(nlogn)\)
优点:快速,且不容易被卡
适用范围:可含负权边单源最短路径,判负环
代码(包含判负环):
bool Spfa(int S) { int t, temp; queue<int> Q; memset(visited, 0, sizeof(visited)); memset(Dis, 0x3f, sizeof(Dis)); memset(In, 0, sizeof(In)); Q.push(S); visited[S] = true; Dis[S] = 0; while (!Q.empty()) { t = Q.front(); Q.pop(); visited[t] = false; for (int i = p[t]; i; i = e[i].next) { temp = e[i].to; if (Dis[temp] > Dis[t] + e[i].w) { Dis[temp] = Dis[t] + e[i].w; if (!visited[temp]) { Q.push(temp); visited[temp] = true; if (++In[temp] > n) //In数组保存进队次数 return false; //负环存在 } } } } return true; //负环不存在 }
时间复杂度:大约\(O(kE)\),其中\(k\)是常数,稀疏图中\(k<2\),最坏情况\(O(VE)\)。
优点:通常情况下较快。
缺点:容易被卡。