如何记录Dijkstra最短路径的过程

Dijkstra算法
   假设找出v0到其他顶点的最短路径
   s[N]初始化为0，如果找到v0到vn的最短路径则把s[n]置一
   dist[N]初始化为v0到其他顶点的直接路径，两个没相连的顶点用MAX值代入
   1.从所有未找到最短路径的顶点中找出dist最小的数值的下标u，所以s[u]置位。
   2.用v0到vu的长度加上vu到其他顶点的长度，如果发现比dist中的小，则更新dist中的数值，但注意此时无需把s[]置位，因为此时得到的并不一定是最短路径。然后跳回1，重新检查v0到s[]中还没被置位的顶点。

通过算法我们可以写代码算出各个最短路径的数值，可是问题来了：最短路径是得到了，可是最短路径该怎么走，我们却还是不知道。总不能再写出多个可能路径，再一一检查距离值和最短路径值是否相同吧。这样得到的结果显然没有太多实际意义。
其实，在之前分析的算法当中，least_dst = dist[u];dist[i] = least_dst + v[u][i];已经包含了顶点到顶点的信息，那么只要把这些信息记录下来，最短路径的过程也就得到了。
那么应该采取什么数据结构来记录这些数据呢？经过了一天多的思考和反复的试验，我最终采用了队列。每个起点到顶点的路径都对应一个记录经历过什么顶点的队列。

为什么选择队列？因为每次更新路径时，其实就是把最短路径经历过的顶点再加上新的终点（在程序中，最终顶点是在确定为最短路径时才入队列的）。而使用队列的出列和入列，就能做到既把顶点值给其他的队列，又能保证本身队列中顶点值按原先顺序存放（每次出列前判断是否是队头元素，如果不是才出列）。
在每次更新前都要清空队列，这样才能使队列记录有效的顶点。当运算得出各个最短路径时，最短路径的过程也就得到了。

 1 #define INF 
 2 
 3 const static int v[N][N] = {...};
 4 
 5 int find_least(int array[], int s[])
 6 {
 7     int min;
 8     int i;
 9     int flag = 0;
10 
11     for (i = 0; i < N; i++)
12     {
13         if (0 == s[i])
14         {
15             if (!flag)
16             {
17                 flag = 1;
18                 min = i;
19             }
20             else
21             {
22                 if (array[i] < array[min])
23                 {
24                     min = i;
25                 }
26             }
27         }
28     }
29 
30     return min;
31 }
32 
33 int main(void)
34 {
35     int s[N] = {0};
36     int dist[N];
37     int start_vet;
38     int u;
39     int least_dst;
40     int i;
41     int count = 0;
42     int temp;
43     sequeue* record[N];
44 
45     printf("input the vertex to start: ");
46     scanf("%d", &start_vet);
47     
48     for (i = 0; i < N; i++)
49     {
50         dist[i] = v[start_vet][i];
51         record[i] = CreateSequeue();
52         EnQueue(record[i], start_vet);
53     }
54     s[start_vet] = 1;
55     
56     while (count++ < N - 1)
57     {
58         u = find_least(dist, s);
59         least_dst = dist[u];
60         s[u] = 1;
61         EnQueue(record[u], u);
62         for (i = 0; i < N; i++)
63         {
64             if (least_dst + v[u][i] < dist[i])
65             {
66                 dist[i] = least_dst + v[u][i];
67                 ClearSequeue(record[i]);
68                 EnQueue(record[i], start_vet);
69                 temp = DeQueue(record[u]);
70                 EnQueue(record[u], temp);
71                 while (GetTopQueue(record[u]) != start_vet)
72                 {
73                     temp = DeQueue(record[u]);
74                     EnQueue(record[i], temp);
75                     EnQueue(record[u], temp);
76                 }
77             }
78         }
79     }
80 
81     //record output
82     
83     return 0;
84 }