分類：
多源最短路徑算法。

作用：
1.求最短路。 2.判斷一張圖中的兩點是否相連。

優(yōu)點：
實現(xiàn)極為簡單

缺點：
只有數(shù)據(jù)規(guī)模較小且時空復(fù)雜度都允許時才可以使用（NOIP上大概不會放出來的吧）。

思想：
3層循環(huán)，第一層枚舉中間點k，第二層與第三層枚舉兩個端點i，j。若有dis[i][j] > dis[i][k] + dis[k][j] 則把dis[i][j]更新成dis[i][k] + dis[k][j]（原理還是很好理解的）。

實現(xiàn)：
(a)初始化：點i，j如果有邊相連，則dis[i][j] = w[i][j]。如果不相連，則dis[i][j] = 0x7fffffff（int極限值），表示兩點不相連（或認為相隔很遠）。?
(b)算法代碼：

for(int k = 1; k <= n; k++) ?//枚舉中間點（必須放最外層）for(int i = 1; i <= n; i++) ?//枚舉端點iif(i != k)for(int j = 1; j <= n; j++) ?//枚舉端點jif(i != j && j != k && dis[i][j] > dis[i][k] + dis[k][j])dis[i][j] = dis[i][k] + dis[k][j];

(c)算法結(jié)束：dis[i][j]得出的就是從i到j(luò)的最短路徑。

Floyed算法變形：
如果是一個沒有邊權(quán)的圖，把相連的兩點間距離設(shè)為dis[i][j] = true，不相連的兩點設(shè)為dis[i][j] = false，用Floyed算法的變形：

for(int k = 1; k <= n; k++) ?//枚舉中間點for(int i = 1; i <= n; i++) ?//枚舉端點iif(i != k)for(int j = 1; j <= n; j++) ?//枚舉端點jif(i != j && j != k)dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);（判斷是否相連）

用這個方法可以判斷一張圖中的兩點是否相連。
例題：

一、

?最短路徑問題

給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。

Input

輸入n,m，點的編號是1~n,然后是m行，每行4個數(shù) a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最后一行是兩個數(shù) s,t;起點s，終點。n和m為0時輸入結(jié)束。?
(1<n<=1000, 0<m<100000, s != t)

Output

輸出 一行有兩個數(shù)， 最短距離及其花費。

Sample Input

3 2 1 2 5 6 2 3 4 5 1 3 0 0

Sample Output

9 11 #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <math.h>using namespace std; #define INF 0x3f3f3f3fint n,m,s,t; int a,b,d,p; int map[1010][1010]; int money[1010][1010];int main() {while(~scanf("%d%d",&n,&m)){if(n==0&&m==0) break;for(int i=1; i<=n; i++)for(int j=1;j<=n;j++)if(i==j) map[i][j]=0;else map[i][j]=INF;for(int i=1;i<=m;i++){scanf("%d%d%d%d",&a,&b,&d,&p);map[a][b]=d;money[a][b]=p;}scanf("%d%d",&s,&t);for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){if(map[i][j]>map[i][k]+map[k][j]){map[i][j]=map[i][k]+map[k][j];money[i][j]=money[i][k]+money[k][j];}}cout << map[s][t] << " " << money[s][t] << endl;}//cout << "Hello world!" << endl;return 0; }

https://blog.csdn.net/weixin_43272781/article/details/83307686?

二、Einbahnstrasse

Einbahnstra??e (German for a one-way street) is a street on which vehicles should only move in one direction. One reason for having one-way streets is to facilitate a smoother flow of traffic through crowded areas. This is useful in city centers, especially old cities like Cairo and Damascus. Careful planning guarantees that you can get to any location starting from any point. Nevertheless, drivers must carefully plan their route in order to avoid prolonging their trip due to one-way streets. Experienced drivers know that there are multiple paths to travel between any two locations. Not only that, there might be multiple roads between the same two locations. Knowing the shortest way between any two locations is a must! This is even more important when driving vehicles that are hard to maneuver (garbage trucks, towing trucks, etc.)?

You just started a new job at a car-towing company. The company has a number of towing trucks parked at the company's garage. A tow-truck lifts the front or back wheels of a broken car in order to pull it straight back to the company's garage. You receive calls from various parts of the city about broken cars that need to be towed. The cars have to be towed in the same order as you receive the calls. Your job is to advise the tow-truck drivers regarding the shortest way in order to collect all broken cars back in to the company's garage. At the end of the day, you have to report to the management the total distance traveled by the trucks.

Input

Your program will be tested on one or more test cases. The first line of each test case specifies three numbers (N , C , and R ) separated by one or more spaces. The city has N locations with distinct names, including the company's garage. C is the number of broken cars. R is the number of roads in the city. Note that 0 < N < 100 , 0<=C < 1000 , and R < 10000 . The second line is made of C + 1 words, the first being the location of the company's garage, and the rest being the locations of the broken cars. A location is a word made of 10 letters or less. Letter case is significant. After the second line, there will be exactly R lines, each describing a road. A road is described using one of these three formats:?


A -v -> B?
A <-v - B?
A <-v -> B?


A and B are names of two different locations, while v is a positive integer (not exceeding 1000) denoting the length of the road. The first format specifies a one-way street from location A to B , the second specifies a one-way street from B to A , while the last specifies a two-way street between them. A , ``the arrow", and B are separated by one or more spaces. The end of the test cases is specified with a line having three zeros (for N , C , and R .)?

The test case in the example below is the same as the one in the figure.?

Output

For each test case, print the total distance traveled using the following format:?


k . V?


Where k is test case number (starting at 1,) is a space, and V is the result.

Sample Input

4 2 5 NewTroy Midvale Metrodale NewTroy <-20-> Midvale Midvale --50-> Bakerline NewTroy <-5-- Bakerline Metrodale <-30-> NewTroy Metrodale --5-> Bakerline 0 0 0

Sample Output

1. 80 /* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=10000; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,c,r,m; char s1[100],s2[100],c1,c2; char str[1005][100]; int a[105][105]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T=0;while(scanf("%d%d%d",&n,&c,&r)!=EOF&&n+c+r){map<string,int>M;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=INF;}}for(int i=0;i<=c;i++){scanf("%s",str[i]);}int cnt=0;for(int i=1;i<=r;i++){scanf("%s %c-%d-%c %s",s1,&c1,&t,&c2,s2);if(!M[s1])M[s1]=++cnt;if(!M[s2])M[s2]=++cnt;int x=M[s1],y=M[s2];if(c1=='<'&&a[y][x]>t)a[y][x]=t;if(c2=='>'&&a[x][y]>t)a[x][y]=t;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){ // if(a[j][k]>a[j][i]+a[i][k]) // a[j][k]=a[j][i]+a[i][k];a[j][k]=min(a[j][k],a[j][i]+a[i][k]);}}}ll ans=0;for(int i=1;i<=c;i++){ans+=a[M[str[0]]][M[str[i]]]+a[M[str[i]]][M[str[0]]];}printf("%d. %lld\n",++T,ans);}//cout << "Hello world!" << endl;return 0; }

https://blog.csdn.net/weixin_43272781/article/details/84943350

?

總結(jié)

以上是生活随笔為你收集整理的Floyed-Warshall算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。