dijkstra算法模板

算法理解见： https://www.bilibili.com/video/av18586085/?p=83
模板:
 1 #define INF 1000000000
 2 
 3 int N;
 4 int dist[101], g[101][101];
 5 int vis[101];
 6 int path[101];    // path[i]表示在最短路径中，i的上一个点
 7 
 8 void init()       // 初始化
 9 {
10     for (int i = 1; i <= N; ++i)
11     {
12         for (int j = 1; j <= N; ++j)
13         {
14             if (i == j)
15                 g[i][j] = 0;
16             else
17                 g[i][j] = INF;
18         }
19     }
20 }
21 
22 void dijkstra(int start)
23 {
24     for(int i = 0; i <= N; ++i)
25     {
26         dist[i] = INF;
27         vis[i] = 0;
28         path[i] = -1;
29     }
30     dist[start] = 0;
31 
32     while (1)
33     {
34         int mark = -1, mindis = INF;
35         for (int i = 1; i <= N; i++)
36         {
37             if (!vis[i] && dist[i] < mindis)
38             {
39                 mindis = dist[i];
40                 mark = i;
41             }
42         }
43         if (mark == -1)    // 找不到未收录的节点，则说明算法结束，退出
44             break;
45         vis[mark] = 1;
46 
47         for (int i = 1; i <= N; i++)
48         {
49             if(!vis[i] && dist[mark] + g[mark][i] < dist[i])
50             {
51                 dist[i] = dist[mark] + g[mark][i];
52                 path[i] = mark;    // 记录路径
53             }
54         }
55     }
56 
57     // 逆序打印路径
58     int k = Sp;        //假设终点是Sp
59     while(k != -1)
60     {
61         printf("%d ", k);
62         k = path[k];
63     }
64     printf("%d", start);
65 }
dijkstra算法 模板

dijkstra算法模板
