最短路徑的了解

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;
}