[作業]利用Dijkstra‘s Algorithm演算法 找出最短捷徑

0  1  2  3  4  5
0| 0 1 6 0

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

0
1| 0 0 5 4 6 0
2| 0 0 0 2 2 0
3| 0 0 0 0 2 3
4| 0 0 0 0 0 4
5| 0 0 0 0 0 0


從0到1權重為1
從0到2權重為6
從1到2權重為3
從1到3權重為4
...

瀏覽完整內容，請先 註冊 或 登入會員

hst326

網路上隨便找都有一堆...
改依下陣列就可以了

1. //  最短路徑問題
   
2. //  戴克斯特拉法 (Dijkstra Algorithm)
   
3. 
   
4. #include <stdio.h>
   
5. 
   
6. #define N 8                            //  節點數量
   
7. #define M 9999                         //  無窮遠
   
8. 
   
9. int a[N+1][N+1] = {{0,0,0,0,0,0,0,0,0},
   
10.                    {0,0,1,7,2,M,M,M,M},
    
11.                    {0,1,0,M,M,2,4,M,M},
    
12.                    {0,7,M,0,M,M,2,3,M},
    
13.                    {0,2,M,M,0,M,M,5,M},
    
14.                    {0,M,2,M,M,0,1,M,M},
    
15.                    {0,M,4,2,M,1,0,M,6},
    
16.                    {0,M,M,3,5,M,M,0,2},
    
17.                    {0,M,M,M,M,M,6,2,0}};
    
18. 
    
19. int main(void)
    
20. {
    
21.     int j, k, p, start, min,
    
22.         leng[N+1],                     //  至節點的距離
    
23.         v[N+1];                        //  確定旗標
    
24.    
    
25.     scanf("%d", &start);               //  輸入起點
    
26.     for(k = 1; k <= N; k++)
    
27.     {
    
28.         leng[k] = M;
    
29.         v[k] = 0;
    
30.     }
    
31.    
    
32.     leng[start] = 0;                   //  起點至起點之距離 = 0
    
33.    
    
34.     for(j = 1; j <= N; j++)
    
35.     {
    
36.         min = M;                       //  min 初始值
    
37.         for(k = 1; k <= N; k++)
    
38.         {
    
39.             if((v[k] == 0)&&(leng[k] < min))
    
40.             {                          //  最短距離
    
41.                 p = k;
    
42.                 min = leng[k];
    
43.             }
    
44.         }
    
45.       
    
46.         v[p] = 1;
    
47.       
    
48.         if(min == M)                   //  圖形沒有連接
    
49.             return 1;
    
50.       
    
51.         //  若經由 p 至 k 的距離比當時的最短距離小，便會執行更新作業
    
52.         for(k = 1; k <= N; k++)
    
53.             if((leng[p]+a[p][k]) < leng[k])
    
54.                 leng[k] = leng[p]+a[p][k];
    
55.     }
    
56.    
    
57.     for(j = 1; j <= N; j++)
    
58.         p rintf("%d -> %d : %d\n", start, j, leng[j]);
    
59.    
    
60.     system( "PAUSE" );
    
61. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

回復

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

hst326

謝謝

that's great for studying,
thanks for your sharing!!!