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