迪傑斯特拉演算法（Dijkstra）

本文非原創~~

　　指定一個點（源點）到其餘各個頂點的最短路徑，也叫做“單源最短路徑”。例如求下圖中的1號頂點到2、3、4、5、6號頂點的最短路徑。

① 將所有的頂點分為兩部分：已知最短路程的頂點集合P和未知最短路徑的頂點集合Q。最開始，已知最短路徑的頂點集合P中只有源點一個頂點。我們這裡用一個book[ i ]數組來記錄哪些點在集合P中。例如對於某個頂點i，如果book[ i ]為1則表示這個頂點在集合P中，如果book[ i ]為0則表示這個頂點在集合Q中。

② 設置源點s到自己的最短路徑為0即dis=0。若存在源點有能直接到達的頂點i，則把dis[ i ]設為e[s][ i ]。同時把所有其它（源點不能直接到達的）頂點的最短路徑為設為∞。

③ 在集合Q的所有頂點中選擇一個離源點s最近的頂點u（即dis[u]最小）加入到集合P。並考察所有以點u為起點的邊，對每一條邊進行鬆弛操作。例如存在一條從u到v的邊，那麼可以通過將邊u->v添加到尾部來拓展一條從s到v的路徑，這條路徑的長度是dis[u]+e[u][v]。如果這個值比目前已知的dis[v]的值要小，我們可以用新值來替代當前dis[v]中的值。

④ 重覆第3步，如果集合Q為空，演算法結束。最終dis數組中的值就是源點到所有頂點的最短路徑。

#include <stdio.h>
int main()
{
    int e[10][10],dis[10],book[10],i,j,n,m,u,v,w,min;
    int inf=99999999; //用inf(infinity的縮寫)存儲一個我們認為的正無窮值
    //讀入n和m，n表示頂點個數，m表示邊的條數
    scanf("%d %d",&n,&m);
    
    //初始化
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) e[i][j]=0;  
            　　else e[i][j]=inf;
              
    //讀入邊
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[u][v]=w;
    }

    //初始化dis數組，這裡是1號頂點到其餘各個頂點的初始路程
    for(i=1;i<=n;i++)
        dis[i]=e[1][i];

    //book數組初始化
    for(i=1;i<=n;i++)
        book[i]=0;
    book[1]=1;
    
    //Dijkstra演算法核心語句
    for(i=1;i<=n-1;i++)
    {
        //找到離1號頂點最近的頂點
        min=inf;
        for(j=1;j<=n;j++)
        {
            if(book[j]==0&&dis[j]<min)
            {
                min=dis[j];
                u=j;
            }
        }
        book[u]=1;
        for(v=1;v<=n;v++)
        {
            if(e[u][v]<inf)
            {
                if(dis[v]>dis[u]+e[u][v]) 
                    dis[v]=dis[u]+e[u][v];
            }
        }    
    }
    
    //輸出最終的結果
    for(i=1;i<=n;i++)
        printf("%d ",dis[i]);
        
    return 0;
}