【算法小总结】迪杰斯特拉(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