图论 —— 最短路 —— Johnson 算法

本文主要是介绍图论 —— 最短路 —— Johnson 算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【概述】

对于单源最短路来说，有时间复杂度为 O(E+VlogV) 要求权值非负的 Dijkstra，时间复杂度为 O(VE) 适用于带负权值的 Bellman Ford

对于全源最短路来说，除了时间复杂度为 O(V*V*V) 利用动态规划思想的 Floyd 算法外，可以认为是单源最短路径的推广，即分别以每个顶点为源点求其至其他顶点的最短距离

对于每个顶点利用 Ford 算法，时间复杂度为 O(V*V*E)，由于图中顶点都是连通的，边的数量可能会比点多，这个时间并没有比 Floyd 更优；而对于每个顶点利用 Dijkstra 算法，时间复杂度为 O(V*E+V*V*logV)，时间复杂度更优，但问题在于 Dijkstra 要求图中边权非负，不适合通用情况

针对 Dijkstra 不能适用于存在负边权的情况，Donald B. Johnson 提出了对所有边的权值进行重赋值的算法，使得边的权值非负，从而可以利用 Dijkstra 进行最短路的计算，即 Johnson 算法

【算法原理】

Johnson 算法的关键在于引入了一个势能函数 h[]，其作为边的映射关系

假设有一个新的点 n+1，其指向其他所有点的边权均为 0，计算这个新点到其他所有点的最短路径数组 h[]：对于边 (u,v)，其权值修改为 dis(u,v)=dis(u,v)+h[u]-h[v]

新增点 n+1 到 u、v 两点的最短路径分别为 h[u]、h[v]，这两点边的权重为 dis(u,v)，那么满足不等式：h[v]<=h[u]+dis(u,v)，那么可以保证新的权重为非负值

对所有边进行重赋值后，再进行 n 次 Dijkstra 来解决 n 个单源最短路问题

设 s 到 t 的最短路经过了 v1,v2,...,vk，那么边的累计和 dis'(s,t)=dis(s,t)+h[s]-h[t]，原来的最短路为：dis(s,t)=dis'(s,t)+h[v]-h[u]

综上，Johnson 算法的描述如下：

1. 对于给定图 G=(V,E)，新增一顶点 S，对 S 到图中所有点都建一条边，得到新图 G'
2. 对图 G' 中点 S 使用 Ford 算法计算单源最短路，得到势能函数 h[]
3. 对原图 G 中所有的边进行重赋值：对于每条边 (u,v)，其新的权值为 dis(u,v)+h[u]-h(v)
4. 对原图 G 的每个顶点运行 Dijkstra，求得全源最短路径

【模版】

vector<Pair> edge[N];
int dis[N][N];
int h[N];
bool vis[N];
void SPFA(int n) {memset(h, INF, sizeof(h));memset(vis, false, sizeof(vis));h[n + 1] = false;queue<int> Q;Q.push(n + 1);while (!Q.empty()) {int u = Q.front();Q.pop();for (int i = 0; i < edge[u].size(); i++) {int v = edge[u][i].first;int w = edge[u][i].second;if (h[v] > h[u] + w) {h[v] = h[u] + w;if (!vis[v]) {vis[v] = true;Q.push(v);}}}}
}
void Dijkstra(int S) {memset(dis, INF, sizeof(dis));dis[S][S] = 0;priority_queue<Pair> Q;Q.push(make_pair(0, S));while (!Q.empty()) {Pair u = Q.top();Q.pop();if (dis[S][u.second] < u.first)continue;for (int i = 0; i < edge[u.second].size(); i++) {int v = edge[u.second][i].first;int w = edge[u.second][i].second;if (dis[S][v] > dis[S][u.second] + w) {dis[S][v] = dis[S][u.second] + w;Q.push(make_pair(dis[S][v], v));}}}
}
void Johnson(int n) {SPFA(n); //计算n+1号点到其他点的距离for (int i = 1; i <= n; i++) //对所有边重新赋值for (int j = 0; j < edge[i].size(); j++)edge[i][j].second += h[i] - h[edge[i][j].first];for (int i = 1; i <= n; i++) //对所有点跑一次DijkDijkstra(i);
}
int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y, w;scanf("%d%d%d", &x, &y, &w);edge[x].push_back(make_pair(y, w));}for (int i = 1; i <= n; i++) //新点到其他点建边,边权为0edge[n + 1].push_back(make_pair(i, 0));Johnson(n);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (dis[i][j] == INF)printf("-1 ");else printf("%d ", dis[i][j] + h[j] - h[i]);printf("\n");}}return 0;
}

 

这篇关于图论 —— 最短路 —— Johnson 算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---