92
人物
【算法小總結】迪傑斯特拉(Dijkstra)求最短路徑
此圖是有向無負權指的圖（弱連通圖）
假設求1到6的最短路徑，用迪傑斯特拉（Dijkstra）算法如何求？
迪傑斯特拉算法像無權最短路徑算法一樣，按階段進行。假設s是起點，在每個階段，迪傑斯特拉算法選擇離s最近的一個頂點v，在v所有未知頂點中選取它能達到的，距離它最短的x頂點的路徑長度D，若D小於s到x的長度(若沒有路就是無窮大)，替換s到x的長度D’，同時聲明s到v的最短路徑是已知的。
其實核心算法就是一個使用貪心選取法則填表的for循環
若是路徑帶價值，加上價值即可，在判斷的時候當路徑長度一樣時，選取
價值較大的
無負權邊迪傑斯特拉基本代碼：
#include<stdio.h>
#include<string.h>
#define INF 0x11111111
int map[1010][1010];
int way[1010],flag[1010];
int main()
{
int i,j,n,m,x,y,z,v,s,t;
while(scanf("%d %d",&n,&m),n!=0&&m!=0)
{
memset(map,INF,sizeof(map));//數組初始化為最大值
for(i=0;i<m;i++)
{
scanf("%d %d %d",&x,&y,&z);
map[x][y]=z;//儲存正反向的路徑長度和花費
map[y][x]=z;
}
scanf("%d %d",&s,&t);
memset(way,INF,sizeof(way));//此數組儲存從s到i的長度
memset(flag,0,sizeof(flag));//標記路徑點是否被加入最短路徑中
flag[s]=1;//起點已經被標記為加入最短路徑
for(i=1;i<=n;i++)//開始賦值
{
way[i]=map[s][i];
}
for(i=1;i<n;i++)
{
int min=INF;
int k=0;
for(j=1;j<=n;j++)//找出一個距離起點最近的路徑
{
if(flag[j]==0&&way[j]<min)
{
min=way[j];
k=j;
}
}
flag[k]=1;
for(j=1;j<=n;j++)//找出距離剛剛選出來的點最近的距離組成新的路徑
{
if(flag[j]==0&&way[k]+map[k][j]<way[j])
{
way[j]=way[k]+map[k][j];
}
}
}
printf("%d\n",way[t]);
}
return 0;
}
input:
7 12
1 2 2
1 4 1
2 5 10
2 4 3
3 6 5
3 1 4
4 6 8
4 7 4
4 3 2
4 2 5
5 7 6
7 6 1
1 6
output:
6
最後更新：2017-04-03 05:39:38