최단 경로 다익스트라 알고리즘

• 방향 그래프 최단 경로를 구하는 알고리즘으로 유명한 다익스트라 알고리즘
• ACM ICPC 대회에서 가끔 요구한다.

1. #include <iostream>
2.  
3. using namespace std;
4.  
5. int main()
6. {
7.     int i,j,k,s,e,min,n=8;
8.     int path[8],path_cnt=0;
9.     // unconnect
10.     const int U=static_cast<unsigned int>(-1)/2;
11.     int data[8][8] = {
12.         {0,2,U,U,U,3,U,U},
13.         {2,0,4,1,U,U,U,U},
14.         {U,4,0,U,3,U,U,U},
15.         {U,1,U,0,3,U,2,U},
16.         {U,U,3,3,0,U,U,4},
17.         {3,U,U,U,U,0,6,U},
18.         {U,U,U,2,U,6,0,4},
19.         {U,U,U,U,4,U,4,0}};
20.     bool v[8];
21.     int distance[8],via[8];
22.  
23.     // 출발, 도착 정점
24.     s=0,e=7;
25.  
26.     // 초기화
27.     for(i=0;i<n;i++)
28.     {
29.         v[i]=false;
30.         distance[i]=U;
31.     }
32.     distance[s]=0;
33.  
34.     // 찾기
35.     for(i=0;i<n;i++)
36.     {
37.         min=U;
38.         for(j=0;j<n;j++)
39.         {
40.             if(v[j]==false && distance[j]<min)
41.             {
42.                 k=j;
43.                 min=distance[j];
44.             }
45.         }
46.         v[k]=true;
47.         if(min==U)
48.             break;
49.         for(j=0;j<n;j++)
50.         {
51.             if(distance[k]==U || data[k][j]==U)
52.                 continue;
53.             if(distance[j]>distance[k]+data[k][j])
54.             {
55.                 distance[j]=distance[k]+data[k][j];
56.                 via[j]=k;
57.             }
58.         }
59.     }
60.     // 최단 비용
61.     cout << distance[e] << endl;
62.     // 최단 경로
63.     k=e;
64.     while(true)
65.     {
66.         path[path_cnt++]=k;
67.         if(k==s)
68.             break;
69.         k=via[k];
70.     }
71.     for(i=path_cnt-1;i>=1;i--)
72.         cout << path[i] << " -> ";
73.     cout << path[i] << endl;
74.  
75.     return 0;
76. }