最短路径的理解

Floyd算法理解

在找一个点到另一个点之间最短距离的时候把尝试把其他的点作为一个中间点来达到缩短这两个点之间的距离的目的，尝试过每个点之后也就能当到当前地图各个点之间的最短距离。

Dijkstra算法理解:

这种算法所寻找的是一个点到其他点之间的最短距离问题，它的具体实现过程是每次寻找距离起始点最近的点，并且将其进行标记，然后找这个点的出点，是否通过他这个点能缩短起始点到这个出点之间的距离，找完这个点所有的出点之后在往下继续寻找除标记外的距离起始点最近的点同样在找这个点的出点，按照上述步骤依次进行，直到找完最后一个距离起始点最近的点和他的所有出口为止算是结束；

再做题时基本上根据题意变化Dijkstra算法中的核心步骤就行

下面是一个Dijkstra算法样例

#include<stdio.h>
int inf=9999999;
int e[300][300],dis[300],book[1010];
int main()
{
     int u,v,w,s,t,n,m,j,i;
     scanf("%d %d",&n,&m);
     //初始是存入的数组
       for(i=0;i<n;i++)
           for(j=0;j<n;j++){
           	if(i==j) e[i][j]=0;
               else e[i][j]=inf;
   		}
       for(i=0; i<m; i++)
       {
           scanf("%d %d %d",&u,&v,&w);
           if(w<e[u][v])
               e[u][v]=e[v][u]=w;//双向道路
       }
       for(i = 0;i < n;i++)
   {
       dis[i]=e[s][i];
       book[i]=0;
   }
   book[s] = 1;
   int min,k;
   for(i=0;i<n;i++)
   {
       min=inf;
       //找最小距离起点的点
       for(j=0;j<n;j++)
       {
           if(book[j]==0&&min>dis[j])
           {
               k=j;
               min=dis[j];
           }
       }
       book[k]=1;
       for(j=0;j<=n;j++)
       {
         if(e[k][j]<inf)//对出点进行判断
         {
         //如果起始点到出点的距离 大于从起始点到中间点再到出点的距离就将出点进行松弛   
            if(dis[j]>dis[k]+e[k][j])
               dis[j]=dis[k]+e[k][j];
         }
       }
     }
   printf("%d\n", dis[n]);
   return 0;
}