Dijkstra算法

基本概念

典型最短路径算法。
从一个节点遍历其余各节点的最短路径算法，解决的是有权图中最短路径问题，它的主要特点是以起始点为中心向外层扩展(广度优先遍历思想)，直到扩展到终点为止。

算法思想

点集S：记录已求出最短路径的节点(以及相应的最短路径长度)
点集U：记录还未确定最短路径的节点(以及该节点到起点D的距离)

1. 初始时，数组S中只有起点D，而数组U中是除起点D之外的节点集合，并且数组U中记录各节点到起点D的距离。如果节点与起点D不相邻，距离设为无穷大。
2. 然后，从数组U中找出路径最短的节点K，并将其加入到数组S中；同时，从数组U中移除节点K。接着，更新数组U中的各节点到起点D的距离。
3. 重复，直到遍历完所有节点。

算法图解

1. 初始时，S只包含起点D；U包含除D外的其他节点，且U中节点的距离为起点D到该节点的距离，如果该节点与起点D不相邻，距离为无穷大。
2. 从U中选出距离最短的节点C，并将节点C加入到S中；同时，从U中移除节点C。然后，更新U中各个节点到起点D的距离。
   $~~~~$之所以更新U中节点的距离，是由于确定了C是求出最短路径过程中的节点，从而可以利用C来更新其它节点的距离；因为起点D到节点v的距离(D,v)可能大于(D,C)+(C,v)的距离。
3. 选取节点E，将E加入到S中，同时更新U中节点的距离。以节点F为例，之前F到D的距离为9；但是将E加入到S之后，F到D的距离为6=(F,E)+(E,D)。
4. 将节点F加入到S中，同时更新U。
5. 将节点G加入到S中，同时更新U。
6. 将节点G加入到S中，同时更新U。
7. 将节点A加入到S中，同时更新U。
   此时，起点D到各个节点的最短距离就计算出来了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。
8. 最后D->A的最优路径为D->E->F->A.

代码实现

S中每增加一个数据时（V1），判断、更新U（Source->V1->Vn）

int *dijkstra_alg(int **a, int Source, int col)
{
    int *dist = calloc(col, sizeof(int));
    bool *visited = calloc(col, sizeof(bool));
    for (int i = 0; i < col; i++)
    {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[Source] = 0;
    int index = 0, u = 0;
    for (int coun = 0; coun < col; coun++)
    {
        int min = INT_MAX;
        for (int i = 0; i < col; i++)
            if (!visited[i] && dist[i] <= min)
            {
                min = dist[i];
                index = i;
            }
        u = index;
        visited[u] = true;
        for (int i = 0; i < col; i++)
            if (!visited[i] && a[u][i] != INT_MAX && dist[u] != INT_MAX && 
                (dist[u] + a[u][i] < dist[i]))
                dist[i] = dist[u] + a[u][i];
    }
    return dist;
}