单源最短路径

说明

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的一条路径

这条路径就是两点之间的最短路径（Shortest Path）

第一个顶点为源点（Source）

最后一个顶点为终点（Destination）

无权图的单源最短路

实现方法：从源点开始，按照非递减的顺序，找出各个顶点的最短路，此类查找类似于图的BFS遍历，但有细微的不同

代码：

void UnWeighted (LGraph graph, int dist[], int path[], Vertex s){
    /* dist[] 存距源点的距离   path[] 存通过结点找到此结点的结点 */
    Queue Q = CreateQueue();
    Vertex v;
    PtrToAdjVNode w;
    dist[s] = 0;    // 初始化源节点
    AddQ(Q, s);
    while (!IsEmpty(Q)){
        v = Delete(Q);
        for (w = graph->g[v]->firstEdge; w; w = w->next)
            if (dist[w->adjv] == -1){
                dist[w->adjv] = dist[v]+1;  // 存入此结点到源节点的距离
                path[w->adjv] = v;  // 存入上个结点的位置
                AddQ(Q, w->adjv);   // 将结点压入队列
            }
    }
}

注：上述代码使用过之前应首先将数组dist[]和path[]各位初始化为-1

解析：上述代码实现方式如下：

将源点对应的 dist[s] 更改为0，并将源点压入队列
弹出源点，并对源点连接的所有结点均作如下处理：记录其与源点的距离并存入 dist[] 数组对应的位置，记录源点的下标于 path[] 数组，将结点压入队列
将队头结点弹出，并对其所连结点做与 2 相似处理：记录其与源点的距离并存入 dist[] 数组对应的位置，记录弹出结点的下标于 path[] 数组，将此结点压入队列
重复 3 ，直至图中所有结点全部进入并被弹出过队列

此算法结束后，如需打印某结点到源结点的最短路径，可以采用栈依靠 path 数组从此结点开始压栈至源节点，然后依次 pop 打印即可

有权图的单源最短路

有了无权图的单源最短路解决方案，有权图的单源最短路便也显得触手可及了

区别：无权图的最短路即经过顶点最少的路径，而有权图的最短路却并非如此，经过的顶点最少的并不一定是最短路

注意：负值圈的影响：由于权值可为负数，有权图可能出现某一回路权值和为负数，那么为了求权值和最小，就会一直在此回路绕圈子，所以，我们首先讨论权值均非负的情况

实现方法：Dijkstra 算法

Vertex FindMinDist(MGraph graph, int dist[], int collected[]){
    Vertex minV, v;
    int minDist = INFINITY;
    for (v = 0; v < graph->nv; v++) {
        if (collected[v] == false && dist[v] < minDist){
            minDist = dist[v];
            minV = v;
        }
    }
    if (minDist < INFINITY)
        return minV;
    else
        return ERROR;
}


bool Dijkstra(MGraph graph, int dist[], int path[], Vertex s){
    int collected[MAXSIZE];
    Vertex v, w;
    /* 初始化：邻接表不存在的边用INFINITY表示 */
    for (v = 0; v < graph->nv; v++) {
        dist[v] = graph->g[s][v];
        if (dist[v] < INFINITY)
            path[v] = s;
        else
            path[v] = -1;
        collected[v] = false;
    }
    /* 先将起点收入集合 */
    dist[s] = 0;
    collected[s] = true;
    while (1){
        /* v = 未被收录顶点中dist最小者 */
        v = FindMinDist(graph, dist, collected);
        if (v == ERROR) // 若v不存在
            break;
        collected[v] = true;    // 收录v
        for (w = 0; w < graph->nv; w++) // 对图中每个顶点w
            if (collected[w] == false && graph->g[v][w] < INFINITY){    // 若w是v的邻接点并且未被收录
                if (graph->g[v][w] < 0) // 有负边
                    return false;
                if (dist[v] + graph->g[v][w] < dist[w]){    // 收录v使得dist[w]变小
                    dist[w] = dist[v] + graph->g[v][w]; // 更新dist[w]
                    path[w] = v;    // 更新s到w的路径
                }
            }
    }
    return true;
}

void Dijkstra() 函数主要分为两部分：初始化，正式运行

初始化：

将 dist[] 数组对应值更新为其到源点的权重，如与源结点不直接相连，则更新为 INFINITY
将与源点相连通的结点对应的 dath[] 更新为源点下标，不相连的更新为 -1
将判断结点是否收录的数组 collected[] 全部置为 false

正式运行：

将源点收录集合，即 collected[s] 置为true
通过 FindMinDist() 函数，查找距离源点最近的结点v并将其收录
遍历v的邻接点，更新其对应的 dist[] 值，存在着两个用处：
- 为邻接点为 INFINITY 的结点赋值
- 查找是否存在比已有路径更短的路径，如果有，将其更新
循环，直至所有结点均被收录

说明

分类：

无权图的单源最短路

有权图的单源最短路