[wikioi]多源最短路

http://wikioi.com/problem/1077/

Floyd算法。精华是三层循环，if (dist(i,k) + dist(k,j) < dist(i,j)) then dist(i,j) = dist(i,k) + dist(k,j)。

但循环的顺序必须k放在最外层，否则会错，因为有可能赋值给dist(i,j)的dist(i,k)和dist(k,j)都还不是最小的，会在之后更新。那么把k放在最外层就对了怎么理解呢？

其本质是一个动态规划：http://lxk3028.blog.163.com/blog/static/37546415200910270028752/

令c[i,j,k]表示从i到j所通过的中间顶点最大不超过k的最短路径的长度，。对于任意的k>0，通过分析可以得到：中间顶点不超过k的i到j的最短路径有两种可能：该路径含或不含中间顶点k。
状态转移方程：c[i,j,k]=min{c[i,j,k-1], c[i,k,k-1]+c[k,j,k-1]}，k＞0。
所以我们平时看到的Floyd算法就是该动态规划的精简版。

#include <cstdio> #include <iostream> #include <algorithm> #include <memory.h> #define MAX(a, b) a>b?a:b #define LEN 105 using namespace std;int n; int graph[LEN][LEN];void init() {memset(graph, 0, sizeof(graph));scanf("%d", &n);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {scanf("%d", &graph[i][j]);}} }void floyd() {for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i != j && i != k && j != k) {if (graph[i][k]+graph[k][j] < graph[i][j]) {graph[i][j] = graph[i][k]+graph[k][j];}}}}} }int main() {init();floyd();int q = 0;scanf("%d", &q);while (q--) {int a = 0;int b = 0;scanf("%d%d", &a, &b);printf("%d\n", graph[a][b]);}return 0; }

　　

转载于:https://www.cnblogs.com/lautsie/p/3386895.html

总结

以上是生活随笔为你收集整理的[wikioi]多源最短路的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。