最短路(Floyed-Warshall、Dijkstra、Bellman-Ford、SPFA)

文章目錄

• Description
• • • Input
    • Output
• 4種做法
• • • 勾股定理
    • 1.Floyed-Warshall算法O(N^3)
    • • • Floyed-Warshall代碼
    • 2.Dijkstra算法O(N^2)
    • • • Dijkstra代碼
    • 3.Bellman-Ford算法O(NE)
    • • • Bellman-Ford代碼
    • 4.SPFA算法O(kE)

Description

平面上有n個點(N<=100)，每個點的坐标均在-10000~10000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點直線的距離。現在的任務是找出從一點到另一點之間的最短路徑。

Input

輸入檔案short.in共有n+m+3行，其中：

第一行為一個整數n。

第2行到第n+1行（共n行），每行的兩個整數x和y，描述一個點的坐标(以一個空格隔開)。

第n+2行為一個整數m，表示圖中的連線個數。

此後的m行，每行描述一條連線，由兩個整數I,j組成，表示第i個點和第j個點之間有連線。

最後一行：兩個整數s和t，分别表示源點和目标點。

Output

輸出檔案short.out僅一行，一個實數(保留兩位小數)，表示從S到T的最短路徑的長度。

4種做法

知道倆點的坐标之後，就可以用勾股定理求出它們之間的距離了。

勾股定理

1. Floyed-Warshall算法O(N^3)

2. Dijkstra算法O(N^2)

3. Bellman-Ford算法O(NE)

4. SPFA算法O(kE)

1.Floyed-Warshall算法O(N^3)

Floyed-Warshall可以算出任何倆個點之間的最優解，而且不排除有負值的情況。

具體算法大概是

枚舉一個點k，接着枚舉，i，j。

然後看看借k從i到j比直接從i到j是否更近一點。

（看上去十分簡單暴力）

Floyed-Warshall代碼

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int t=0,n,m,x[101],y[101];
double D[101][101];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	int xx,yy;
	memset(D,0x7f,sizeof(D));
	for(int i=1;i<=m;++i){
		scanf("%d%d",&xx,&yy);
		D[xx][yy]=D[yy][xx]=sqrt(pow(double(x[xx]-x[yy]),2)+pow(double(y[xx]-y[yy]),2));
	}
	int q,z;
	scanf("%d%d",&q,&z);
	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&&k!=j&&D[i][j]>D[i][k]+D[k][j])
	        D[i][j]=D[i][k]+D[k][j];
	printf("%0.2f",D[q][z]);
}           

2.Dijkstra算法O(N^2)

Dijkstra無法處理帶有負權值的圖。

它從一個點開始，尋找到最近的一個點，判斷、改變那個點連接配接的其他點 到原點的距離。然後再找另外的一個最近的點，重複操作。

Dijkstra代碼

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int t=0,n,m,x[101],y[101];
double D[101][101],c[101];
bool B[101];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	int xx,yy;
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=n;++j)
	    D[i][j]=1e30;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&xx,&yy);
		D[xx][yy]=D[yy][xx]=sqrt((x[xx]-x[yy])*(x[xx]-x[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]));
	}
	int q,z;
	scanf("%d%d",&q,&z);
	for(int i=1;i<=n;++i)
	  c[i]=D[q][i];
	B[q]=1;
	c[q]=0;
	for(int i=1;i<n;++i){ 
		double minn=1e30;
		int k=0;
		for(int j=1;j<=n;++j) 
           if((!B[j])&&c[j]<minn){
                minn=c[j];
                k=j;
            }
        if(k==0) break;
        B[k]=1;
        for(int j=1;j<=n;j++)
           if(c[j]>c[k]+D[k][j]&&!B[j]) 
             c[j]=c[k]+D[k][j];
	}
	printf("%0.2lf\n",c[z]);
}           

3.Bellman-Ford算法O(NE)

Bellman-Ford無法處理帶負權回路的情況。

是以它是可以判斷一個圖是否有環的！（？？

原理大概是枚舉所有的邊，然後更新邊連接配接的倆個點的距離。如果n輪過後，所有的點都沒有更新，即現在就是最優解了。

Bellman-Ford代碼

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int n,x[101],y[101],m,A[10001],B[10001],q,z;
double K[101],Z[10001];
bool L;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&A[i],&B[i]);
		Z[i]=sqrt(double((x[A[i]]-x[B[i]])*(x[A[i]]-x[B[i]]))
		+double((y[A[i]]-y[B[i]])*(y[A[i]]-y[B[i]])));
	}
	scanf("%d%d",&q,&z);
	memset(K,0x7f,sizeof(K));
	K[q]=0;
	for(int i=1;i<n;++i){  //這個算法頂多計算n-1輪，不然就是圖上存在環

		L=false;
		for(int j=1;j<=m;++j){  //枚舉邊
			if(K[A[j]]+Z[j]<K[B[j]])  //是否能更新
			{
				K[B[j]]=K[A[j]]+Z[j];
				L=1;
			}
			if(K[B[j]]+Z[j]<K[A[j]])
			{
				K[A[j]]=K[B[j]]+Z[j];
				L=1;
			}
		
		}
		if(!L) break;  //沒有更新過
	}
	printf("%.2lf",K[z]);
	return 0;
}           

4.SPFA算法O(kE)

關于SPFA，（他死了），用于求一個點到其他點的最優距離

對比Bellman-Ford算法，SPFA少了更多的沉餘操作。我們發現，Bellman-Ford 中，有很多邊進行了沒用的計算，是以SPFA算法就隻算了新更新的點所連接配接的邊。

（是以，鄰接表派上用場了！！！）

這個算法莫明像Bellman-Ford與Dijkstra的結合體？？？

#include<cstdio>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
int n,m,L[101],x[101],y[101],t=0;
double C[101],J[101][101];
bool B[101];
struct KKK{
	int y,next;
} a[10001];
void SPFA(int k){
	queue<int> Q;
	Q.push(k);
	memset(C,0x7f,sizeof(C));
	C[k]=0;
	while(Q.size()){  //還有更新過的點
		int l=Q.front();  //取出隊頭
		Q.pop();  //彈出
		B[l]=false;
		for(int i=L[l];i;i=a[i].next)  //枚舉連接配接的點
		  if(C[a[i].y]>C[l]+J[a[i].y][l]){  //如果可以更新距離
		  	C[a[i].y]=C[l]+J[a[i].y][l];
		  	if(!B[a[i].y])  //壓入隊列
		  		Q.push(a[i].y);
		  }
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	int l1,l2;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&l1,&l2);
		J[l1][l2]=J[l2][l1]=sqrt((x[l1]-x[l2])*(x[l1]-x[l2])+(y[l1]-y[l2])*(y[l1]-y[l2]));  
		//計算直線距離
		a[++t].y=l2;a[t].next=L[l1];L[l1]=t;  //鄰接表儲存
		a[++t].y=l1;a[t].next=L[l2];L[l2]=t;
	}
	scanf("%d%d",&l1,&l2);
	SPFA(l1);
	printf("%.2f",C[l2]);
}