图论-多源最短路径（Floyd算法）

电玩女神 2022-12-11 15:07 177阅读 0赞

### 文章目录 ###

*  Floyd
 *  模板
 *  例题
 *   *  POJ-3259（负圈）
     *  HDU-1385（打印路径）
     *  HDU-1599（最小环）
     *  HDU-1704（传递闭包）
     *  HDU-3631（变形）

# Floyd #

--------------------

Floyd算法是一次性求所有结点之间的最短距离，能处理负权边的图，程序比暴力的DFS更简单，但是复杂度是 O ( n 3 ) O(n^3) O(n3)，只适合 n < 200 n<200 n<200的情况。  
Floyd运用了动态规划的思想，求 i 、 j i、j i、j两点的最短距离，可分两种情况考虑，即经过图中某个点 k k k的路径和不经过点 k k k的路径，取两者中的最短路径。

*  判断负圈  
    眼尖的人儿可能发现邻接矩阵 m p mp mp中， m p \[ i \] \[ i \] mp\[i\]\[i\] mp\[i\]\[i\]并没有赋初值0，而是 i n f inf inf。并且计算后 m p \[ i \] \[ i \] mp\[i\]\[i\] mp\[i\]\[i\]的值也不是 0 0 0，而是 m p \[ i \] \[ i \] = m p \[ i \] \[ u \] + … … + m p \[ v \] \[ i \] mp\[i\]\[i\]=mp\[i\]\[u\]+……+mp\[v\]\[i\] mp\[i\]\[i\]=mp\[i\]\[u\]\+……\+mp\[v\]\[i\]，即从外面绕一圈回来的最短路径，而这正用于判断负圈，即 m p \[ i \] \[ i \] < 0 mp\[i\]\[i\]<0 mp\[i\]\[i\]<0。

相关变形结合题目讲，如：负圈、打印路径、最小环、传递闭包  
记录坑点：**重复边**，保留最小的那个。

# 模板 #

--------------------

void floyd() { 
    	for (int k = 1; k <= n; k++)
    		for (int i = 1; i <= n; i++)
    			if (mp[i][k] != inf)  //优化
    				for (int j = 1; j <= n; j++)
    					if (mp[i][j] > mp[i][k] + mp[k][j])
    						mp[i][j] = mp[i][k] + mp[k][j];
    }

# 例题 #

--------------------

## POJ-3259（负圈） ##

[POJ-3259 Wormholes][]

> **Description**  
> While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1…N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.  
> As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself ) .  
> To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.  
> **Input**  
> Line 1: A single integer, F. F farm descriptions follow.  
> Line 1 of each farm: Three space-separated integers respectively: N, M, and W  
> Lines 2…M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.  
> Lines M+2…M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.  
> **Output**  
> Lines 1…F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).  
> **Sample Input**  
> 2  
> 3 3 1  
> 1 2 2  
> 1 3 4  
> 2 3 1  
> 3 1 3  
> 3 2 1  
> 1 2 3  
> 2 3 4  
> 3 1 8  
> **Sample Output**  
> NO  
> YES  
> **Hint**  
> For farm 1, FJ cannot travel back in time.  
> For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

**分析**：  
给定若干双向正值边和单向负值边，问是否存在负圈（使其时光倒流回到原点）。  
所以在第二重循环，求完第i个结点后判断。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 502;
    int t, n, m, w, x, y, z;
    int mp[maxn][maxn];
    bool floyd() { 
    	for (int k = 1; k <= n; k++)
    		for (int i = 1; i <= n; i++)
    			if (mp[i][k] != inf) { 
    				for (int j = 1; j <= n; j++)
    					if (mp[i][j] > mp[i][k] + mp[k][j])
    						mp[i][j] = mp[i][k] + mp[k][j];
    				if (mp[i][i] < 0)return true;
    			}
    	return false;
    }
    int main() { 
    	scanf("%d", &t);
    	while (t--) { 
    		scanf("%d%d%d", &n, &m, &w);
    		memset(mp, inf, sizeof(mp));
    		for (int i = 0; i < m; i++) { 
    			scanf("%d%d%d", &x, &y, &z);
    			if (z < mp[x][y]) //注意坑：重边
    				mp[x][y] = mp[y][x] = z;
    		}
    		for (int i = 0; i < w; i++) { 
    			scanf("%d%d%d", &x, &y, &z);
    			mp[x][y] = -z;
    		}
    		if (floyd())puts("YES");
    		else puts("NO");
    	}
    	return 0;
    }

## HDU-1385（打印路径） ##

[HDU-1385 Minimum Transport Cost][]

> **Problem Description**  
> These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts:  
> The cost of the transportation on the path between these cities, and  
> a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities.  
> You must write a program to find the route which has the minimum cost.  
> **Input**  
> First is N, number of cities. N = 0 indicates the end of input.  
> The data of path cost, city tax, source and destination cities are given in the input, which is of the form:  
> a11 a12 … a1N  
> a21 a22 … a2N  
> …  
> aN1 aN2 … aNN  
> b1 b2 … bN  
> c d  
> e f  
> …  
> g h  
> where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, …, and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form:  
> **Output**  
> From c to d :  
> Path: c–>c1–>…–>ck–>d  
> Total cost : …  
> …  
> From e to f :  
> Path: e–>e1–>…–>ek–>f  
> Total cost : …  
> Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case.  
> **Sample Input**  
> 5  
> 0 3 22 -1 4  
> 3 0 5 -1 -1  
> 22 5 0 9 20  
> \-1 -1 9 0 4  
> 4 -1 20 4 0  
> 5 17 8 3 1  
> 1 3  
> 3 5  
> 2 4  
> \-1 -1  
> 0  
> **Sample Output**  
> From 1 to 3 :  
> Path: 1–>5–>4–>3  
> Total cost : 21  
> From 3 to 5 :  
> Path: 3–>4–>5  
> Total cost : 16  
> From 2 to 4 :  
> Path: 2–>1–>5–>4  
> Total cost : 17

**分析**：  
输出路径，多个答案则输出字典序最小的，无法到达输出-1。  
读入邻接表， c o s t \[ \] cost\[\] cost\[\]记录每个城市额外费用， p a t h \[ \] \[ \] path\[\]\[\] path\[\]\[\]记录路径，比如 p \[ i \] \[ j \] = k p\[i\]\[j\]=k p\[i\]\[j\]=k表示 i i i到 j j j的路径是 i i i先到 k k k，再从 k k k到 j j j，floyd()里维护即可。然后处理下输出(比较恶心)。

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 1003;
    int mp[maxn][maxn], path[maxn][maxn];//邻接矩阵、路径
    int n, x, y, u, v, cost[maxn];//额外费用
    void floyd() { 
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			if(mp[i][k]!=inf)
    				for (int j = 1; j <= n; j++) { 
    					if (mp[i][j] > mp[i][k] + mp[k][j] + cost[k]) { 
    						mp[i][j] = mp[i][k] + mp[k][j] + cost[k];
    						path[i][j] = path[i][k];
    					}
    					if (mp[i][j] == mp[i][k] + mp[k][j] + cost[k]) { 
    						if (path[i][j] > path[i][k])  //字典序
    							path[i][j] = path[i][k];
    					}
    				}
    }
    int main() { 
    	while (~scanf("%d", &n) && n) { 
    		for (int i = 1; i <= n; i++) { 
    			for (int j = 1; j <= n; j++) { 
    				path[i][j] = j;
    				scanf("%d", &mp[i][j]);
    				if (mp[i][j] == -1)
    					mp[i][j] = inf;
    			}
    		}
    		for (int i = 1; i <= n; i++)
    			scanf("%d", &cost[i]);
    		floyd();
    		while (scanf("%d%d", &x, &y)) { 
    			if (x == -1 && y == -1)break;
    			u = x, v = y;
    			printf("From %d to %d :\n", x, y);
    			printf("Path: %d", x);
    			while (x != y) { 
    				printf("-->%d", path[x][y]);
    				x = path[x][y];
    			}
    			printf("\n");
    			if (mp[u][v] < inf)
    				printf("Total cost : %d\n", mp[u][v]);
    			else printf("-1\n");
    			printf("\n");
    		}
    	}
    	return 0;
    }

## HDU-1599（最小环） ##

[HDU-1599 find the mincost route][]

> **Problem Description**  
> 杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,…VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。  
> **Input**  
> 第一行是2个整数N和M（N <= 100, M <= 1000)，代表景区的个数和道路的条数。  
> 接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需要花费c元(c <= 100)。  
> **Output**  
> 对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出"It’s impossible.".  
> **Sample Input**  
> 3 3  
> 1 2 1  
> 2 3 1  
> 1 3 1  
> 3 3  
> 1 2 1  
> 1 2 3  
> 2 3 1  
> **Sample Output**  
> 3  
> It’s impossible

**分析**：  
求最小环，用 d i s \[ \] dis\[\] dis\[\]记录原距离，当枚举中间结点 k k k时，首先知道任意两点 i i i、 j j j不经过 k k k的最短路径 m p \[ i \] \[ j \] mp\[i\]\[j\] mp\[i\]\[j\]（原floyd的二三重循环后更新 m p \[ i \] \[ j \] mp\[i\]\[j\] mp\[i\]\[j\]得到经过 k k k的最短路），此时枚举 i i i和 j j j得到一个经过 k k k的环（ i i i到 j j j， j j j到 k k k， k k k到 i i i）并记录最小答案即可，即 m p \[ i \] \[ j \] + d i s \[ j \] \[ k \] + d i s \[ k \] \[ i \] mp\[i\]\[j\] + dis\[j\]\[k\] + dis\[k\]\[i\] mp\[i\]\[j\]\+dis\[j\]\[k\]\+dis\[k\]\[i\]。  
注意题目 i j k ijk ijk不能相同，还有坑点：long long

> （插播反爬信息 ）博主CSDN地址：[https://wzlodq.blog.csdn.net][https_wzlodq.blog.csdn.net]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define inf 0x3f3f3f3f
    const int maxn = 102;
    ll mp[maxn][maxn], dis[maxn][maxn];
    ll n, m, a, b, c, ans;
    void floyd() { 
    	for (int k = 1; k <= n; k++) { 
    		
    		for (int i = 1; i < k; i++)  //枚举ij
    			for (int j = i + 1; j < k; j++)  //注意ijk不能相同
    				if (ans > mp[i][j] + dis[j][k] + dis[k][i])
    					ans = mp[i][j] + dis[j][k] + dis[k][i];
    					
    		for (int i = 1; i <= n; i++)  //原floyd
    			for (int j = 1; j <= n; j++)
    				if (mp[i][j] > mp[i][k] + mp[k][j])
    					mp[i][j] = mp[i][k] + mp[k][j];
    
    	}
    }
    int main() { 
    	while (~scanf("%lld%lld", &n, &m)) { 
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= n; j++)
    				if (i == j)mp[i][j] = dis[i][j] = 0;
    				else mp[i][j] = dis[i][j] = inf;
    		while (m--) { 
    			scanf("%lld%lld%lld", &a, &b, &c);
    			if (c < mp[a][b]) //防重边，怕了怕了
    				mp[a][b] = dis[a][b] = c;
    			if (c < mp[b][a]) 
    				mp[b][a] = dis[b][a] = c;
    		}
    		ans = inf;
    		floyd();
    		if (ans == inf)puts("It's impossible.");
    		else printf("%lld\n", ans);
    	}
    	return 0;
    }

## HDU-1704（传递闭包） ##

[HDU-1704 Rank][]

> **Problem Description**  
> there are N ACMers in HDU team.  
> ZJPCPC Sunny Cup 2007 is coming, and lcy want to select some excellent ACMers to attend the contest. There have been M matches since the last few days(No two ACMers will meet each other at two matches, means between two ACMers there will be at most one match). lcy also asks"Who is the winner between A and B?" But sometimes you can’t answer lcy’s query, for example, there are 3 people, named A, B, C.and 1 match was held between A and B, in the match A is the winner, then if lcy asks “Who is the winner between A and B”, of course you can answer “A”, but if lcy ask “Who is the winner between A and C”, you can’t tell him the answer.  
> As lcy’s assistant, you want to know how many queries at most you can’t tell lcy(ask A B, and ask B A is the same; and lcy won’t ask the same question twice).  
> **Input**  
> The input contains multiple test cases.  
> The first line has one integer,represent the number of test cases.  
> Each case first contains two integers N and M(N , M <= 500), N is the number of ACMers in HDU team, and M is the number of matchs have been held.The following M lines, each line means a match and it contains two integers A and B, means A wins the match between A and B.And we define that if A wins B, and B wins C, then A wins C.  
> **Output**  
> For each test case, output a integer which represent the max possible number of queries that you can’t tell lcy.  
> **Sample Input**  
> 3  
> 3 3  
> 1 2  
> 1 3  
> 2 3  
> 3 2  
> 1 2  
> 2 3  
> 4 2  
> 1 2  
> 3 4  
> **Sample Output**  
> 0  
> 0  
> 4  
> **Hint**  
> in the case3, if lcy ask (1 3 or 3 1) (1 4 or 4 1) (2 3 or 3 2) (2 4 or 4 2), then you can’t tell him who is the winner.

**分析**：  
求多少组关系没法确定，传递闭包，比如1->2，2->3（mp\[1\]\[2\]=1、mp\[2\]\[3\]=1），由传递关系得1->3，即原来的mp\[1\]\[3\]置1。

#include <bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 502;
    int t, n, m, x, y, ans;
    int mp[maxn][maxn];
    void floyd() { 
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; mp[i][k] && j <= n; j++)
                    mp[i][j] |= mp[i][k] & mp[k][j]; //通过k传递,或运算
    }
    int main() { 
        scanf("%d", &t);
        while (t--) { 
            scanf("%d %d", &n, &m);
            memset(mp, 0, sizeof(mp));
            while (m--) { 
                scanf("%d %d", &x, &y);
                mp[x][y] = 1;
            }
            floyd();
            ans = 0;
            for (int i = 1; i <= n; i++)  //统计答案
                for (int j = i + 1; j <= n; j++)
                    if (!mp[i][j] && !mp[j][i])
                        ans++;
            printf("%d\n", ans);
        }
        return 0;
    }

## HDU-3631（变形） ##

[HDU-3631 Shortest Path][]

> **Problem Description**  
> When YY was a boy and LMY was a girl, they trained for NOI (National Olympiad in Informatics) in GD team. One day, GD team’s coach, Prof. GUO asked them to solve the following shortest-path problem.  
> There is a weighted directed multigraph G. And there are following two operations for the weighted directed multigraph:  
> (1) Mark a vertex in the graph.  
> (2) Find the shortest-path between two vertices only through marked vertices.  
> For it was the first time that LMY faced such a problem, she was very nervous. At this moment, YY decided to help LMY to analyze the shortest-path problem. With the help of YY, LMY solved the problem at once, admiring YY very much. Since then, when LMY meets problems, she always calls YY to analyze the problems for her. Of course, YY is very glad to help LMY. Finally, it is known to us all, YY and LMY become programming lovers.  
> Could you also solve the shortest-path problem?  
> **Input**  
> The input consists of multiple test cases. For each test case, the first line contains three integers N, M and Q, where N is the number of vertices in the given graph, N≤300; M is the number of arcs, M≤100000; and Q is the number of operations, Q ≤100000. All vertices are number as 0, 1, 2, … , N - 1, respectively. Initially all vertices are unmarked. Each of the next M lines describes an arc by three integers (x, y, c): initial vertex (x), terminal vertex (y), and the weight of the arc ©. (c > 0) Then each of the next Q lines describes an operation, where operation “0 x” represents that vertex x is marked, and operation “1 x y” finds the length of shortest-path between x and y only through marked vertices. There is a blank line between two consecutive test cases.  
> End of input is indicated by a line containing N = M = Q = 0.  
> **Output**  
> Start each test case with “Case \#:” on a single line, where \# is the case number starting from 1.  
> For operation “0 x”, if vertex x has been marked, output “ERROR! At point x”.  
> For operation “1 x y”, if vertex x or vertex y isn’t marked, output “ERROR! At path x to y”; if y isn’t reachable from x through marked vertices, output “No such path”; otherwise output the length of the shortest-path. The format is showed as sample **output.**  
> There is a blank line between two consecutive test cases.  
> **Sample Input**  
> 5 10 10  
> 1 2 6335  
> 0 4 5725  
> 3 3 6963  
> 4 0 8146  
> 1 2 9962  
> 1 0 1943  
> 2 1 2392  
> 4 2 154  
> 2 2 7422  
> 1 3 9896  
> 0 1  
> 0 3  
> 0 2  
> 0 4  
> 0 4  
> 0 1  
> 1 3 3  
> 1 1 1  
> 0 3  
> 0 4  
> 0 0 0  
> **Sample Output**  
> Case 1:  
> ERROR! At point 4  
> ERROR! At point 1  
> 0  
> 0  
> ERROR! At point 3  
> ERROR! At point 4

**分析**：  
在有向图中两种操作：①标记一个点②在标记点上查询最短路径。查询虽然很多但每个点的标记操作只有一次（重复标记输出error），那么我们对标记操作就是把标记点作为中间结点k，去更新其余的最短路径就好了(floyd二三重循环)。  
注意下标输入从0开始，还有格式。

#include <bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 302;
    int t = 0, n, m, q, u, v, w;
    int mp[maxn][maxn];
    bool flag[maxn]; //记录是否标记
    void floyd(int k) { 
    	for (int i = 0; i < n; ++i)
    		for (int j = 0; j < n; ++j)
    			if (mp[i][j] > mp[i][k] + mp[k][j])
    				mp[i][j] = mp[i][k] + mp[k][j];
    }
    int main(){ 
    	while (~scanf("%d %d %d", &n, &m, &q)) { 
    		if (n == 0 && m == 0 && q == 0) break;
    		if (t != 0)printf("\n"); //谜之格式
    		printf("Case %d:\n", ++t);
    		memset(mp, inf, sizeof(mp));
    		memset(flag, false, sizeof(flag));
    		for (int i = 0; i <= n; ++i)
    			mp[i][i] = 0;
    		while (m--) { 
    			scanf("%d %d %d", &u, &v, &w);
    			if (w < mp[u][v])
    				mp[u][v] = w;
    		}
    		while (q--) { 
    			scanf("%d", &w);
    			if (w == 0) { 
    				scanf("%d", &u);
    				if (flag[u])printf("ERROR! At point %d\n", u);
    				else { 
    					flag[u] = true;
    					floyd(u);
    				}
    			}
    			else { 
    				scanf("%d %d", &u, &v);
    				if (!(flag[u] && flag[v]))
    					printf("ERROR! At path %d to %d\n", u, v);
    				else if (mp[u][v] == inf)
    					printf("No such path\n");
    				else printf("%d\n", mp[u][v]);
    				
    			}
    		}
    	}
    	return 0;
    }

*ps：这是我有域名(博客六级)后的第一篇博客，加油*(。・∀・)ノ

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://wzlodq.blog.csdn.net][https_wzlodq.blog.csdn.net]  
> *如果文章对你有帮助，记得一键三连❤*

[POJ-3259 Wormholes]: https://vjudge.net/problem/POJ-3259
[HDU-1385 Minimum Transport Cost]: https://vjudge.net/problem/HDU-1385
[HDU-1599 find the mincost route]: https://vjudge.net/problem/HDU-1599
[https_wzlodq.blog.csdn.net]: https://wzlodq.blog.csdn.net
[HDU-1704 Rank]: https://vjudge.net/problem/HDU-1704
[HDU-3631 Shortest Path]: https://vjudge.net/problem/HDU-3631