【圖】最短路徑——Floyed算法和Dijkstra算法

最短路徑問題(floyed.cpp dijkstra.cpp)

題目描述
平面上有n個點(n<=100)，每個點的坐標均在-10000～10000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離。現在的任務是找出從一點到另一點之間的最短路徑。
輸入
第1行：1個整數n
第2..n+1行：每行2個整數x和y，描述了一個點的坐標
第n+2行：1個整數m，表示圖中連線的數量
接下來有m行，每行2個整數i和j，表示第i個點和第j個點之間有連線
最后1行：2個整數s和t，分別表示源點和目標點
輸出
第1行：1個浮點數，表示從s到t的最短路徑長度，保留2位小數
樣例輸入
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
樣例輸出

3.41

#------------------------------------------------------------------------------#

最短路徑也是有很多方法的，這里就講講Floyed和Dijkstra。

Floyed：

這種算法比較好理解，且可以求任意兩點間的最短路徑，但速度很慢，為O(N^3)。

首先，需要k[i][j]存從第i點到第j點間的最短路徑，如果它們不相連，則為∞（無窮大）（在這里可以設為0x7fffffff，0x表示后面的數為16進制，7fffffff即是16進制數，化為10進制等于2147483647）。

然后需要3層循環，第一層：需要經過的點p，第二、三層起點i和終點j，然后就開始推，很像動規的，“狀態轉移方程”為：k[i][j]=min(k[i][j],k[i][p]+k[p][j])

這樣不用考慮兩點沒聯通的情況嗎？之前的∞就有作用了，如果兩點沒聯通的話是賦不了值的。

代碼（Floyed）：

#include<cstdio>
#include<cmath>
struct p
{int x,y;
}a[102];//這個結構體是存平面直角坐標系的
int f[102][102];
double k[102][102];
int n,m,hhd;
int main()
{//freopen("floyed.in","r",stdin);//freopen("floyed.out","w",stdout);//文件輸入輸出int b,e;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);scanf("%d",&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);f[x][y]=f[y][x]=1;//鄰接數組標記}scanf("%d%d",&b,&e);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(f[i][j])//如果兩點有連接k[i][j]=sqrt(pow(a[i].x-a[j].x,2.0)+pow(a[i].y-a[j].y,2.0));//求兩點距離，存入k數組elsek[i][j]=0x7fffffff;//反之則設為極大值for(int p=1;p<=n;p++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(k[i][j]>k[i][p]+k[p][j])k[i][j]=k[i][p]+k[p][j];//開始算法printf("%.2lf",k[b][e]);//輸出從起點（b）到終點（e）的最短路徑return 0;
}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?----我只是個小分割線----

Dijkstra：

此算法較（只是較前一種）快，時間復雜度為O(N^2)，注意，它不能處理負邊權的情況。

而且這個只能求從一個起點（單源點）到其他任何點的距離，但解決這道題足夠了。

一個一維數組dis[i]表示起點到i點的最短距離，k數組與上同，還需要一個bool數組判斷該點是否用過。

思路：從起點到某個點一定會經過一個及以上的“中間點”，可以發現從起點到i點的最短路徑中的每一個“中間點”到起點的距離都是相等的，就像動態規劃的“最優子結構”性質，所以只要找出每個點的最短路徑，即可知道起點到終點的最短路徑。

為什么不能處理負邊權呢？

如圖，假如想要從1到3，最短的顯然為1->2->3，共-2，但Dijkstra算法會先選擇直接到3，因為這樣為1，所以答案錯誤。

代碼（Dijkstra）：

#include<cstdio>
#include<cmath>
#include<cstring>
struct p
{int x,y;
}a[102];
int _f[102][102];
bool f[102];
double k[102][102],dis[102];
int n,m;
int main()
{//freopen("dijkstra.in","r",stdin);//freopen("dijkstra.out","w",stdout);int b,e;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);scanf("%d",&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);_f[x][y]=_f[y][x]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(_f[i][j])k[i][j]=sqrt(pow(a[i].x-a[j].x,2.0)+pow(a[i].y-a[j].y,2.0));elsek[i][j]=0x7fffffff;//以上與Floyed相同scanf("%d%d",&b,&e);f[b]=1;for(int i=1;i<=n;i++)dis[i]=k[b][i];//將距離存進去for(int i=1;i<=n-1;i++){int p=0x7fffffff,w=0;//p為當前最小值，w為“中間點”下標for(int j=1;j<=n;j++)if(f[j]==0&&dis[j]<p){w=j;p=dis[j];//更新最小值}//查找“中間點”if(w==0)break;//如果全部沒有，則表示找完了f[w]=1;//標記此點已用for(int j=1;j<=n;j++)if(dis[w]+k[w][j]<dis[j])dis[j]=dis[w]+k[w][j];//開始找進過w的最小值}printf("%.2lf",dis[e]);//輸出return 0;
}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?By WZY