图论:8.3.单源最短路径

大部分设置标记和纠正标记法可以融合为同一形式：
 
genericShortestPathAlgorithm(带权简单图 digraph, 顶点 first) {

    for 所有顶点 v 
        currDist(v) = 无穷大;
    currDist(first) = 0;
    初始化 toBeChecked;
    while toBeChecked 非空 {
        v = toBeChecked中的一个顶点;
        从 toBeChecked 中删除 v;
        for 所有和 v 邻接的顶点 u {
            if currDist(u) > currDist(v) + weight(edge(vu)) {
                currDist(u) = currDist(v) + weight(edge(vu));
                predecessor(u) = v;
                如果 u 不属于 toBeChecked ，就把它添加进去;
            }    //end if
        }    //end for
    }    //end while
}    //end algorithm

说明：

    1.在这个通用算法中，标记由两个元素组成：label(v) = (currDist(v), predecessor(v))

    2.这个算法存在两个问题：集合 toBeChecked 的结构和赋值语句"v = toBeChecked 中的一个顶点;"中为 v 赋新值的顺序。很明显toBeChecked 的结构可以确定为 v 选择新值的顺序，它也同样可以确定算法的效率。

    3.区分设置标记法和纠正标记法的是“为 v 选择值的方法”,v 是toBeChecked中当前距离最小的节点。

一.第一个设置标记算法是由 Dijkstra 提出的。

DijkstraAlgorithm(带权简单图 digraph, 顶点 first) {

    for 所有顶点 v 
        currDist(v) = 无穷大;
    currDist(first) = 0;
    toBeChecked = 所有顶点;
    while toBeChecked 非空 {
        v = toBeChecked 中 currDist(v) 最小的一个顶点;
        从 toBeChecked 中删除 v;
        for toBeChecked 中所有和 v 邻接的顶点 u {
            if currDist(u) > currDist(v) + weight(edge(vu))
                currDist(u) = currDist(v) + weight(edge(vu));
                predecessor(u) = v;
            }    //end if
        }    //end for
    }    //end while
}    //end algorithm

说明：
    Dijkstra算法的复杂性是 O(|v|^2)。它不是通用的，因为它不能处理有负权的图，原因在于当前距离从无穷大设置成一个数值之后的顶点将不再被检测。

二.第一个纠正标记算法是由 Lester Ford 设计的。
    它在整个图处理完成之前不会永久性确定任何节点的最短距离。它比 Dijkstra 算法功能更强，因为它可以处理带负权的图(但不能是有负环的图)。和算法原来形式的需要一样，必须检测所有的边来尽可能地缩短顶点之间的当前距离。

FordAlgorithm(带权简单图 digraph, 顶点 first) {

    for 所有顶点 v 
        currDist(v) = 无穷大;
    currDist(first) = 0;
    while 存在一条边 vu 使得 currDist(u) > currDist(v) + weight(edge(vu))
        currDist(u) = currDist(v) + weight(edge(vu));
}    //end algorithm

说明：

    为了给监视的边加上某种顺序，边可以按字母顺序排序，这样这个算法可以在整个序列中循环并在需要的时候调整任何顶点的当前距离。这个算法的复杂性为 O(|V||E|)。

通用的纠正标记算法。

labelCorrectingAlgorithm(带权简单图 digraph, 顶点 first) {

    for 所有顶点 v 
        currDist(v) = 无穷大;
    currDist(first) = 0;
    toBeChecked = {first};
    while toBeChecked 非空 {
        v = toBeChecked中的一个顶点;
        从 toBeChecked 中删除 v;
        for 所有和 v 邻接的顶点 u {
            if currDist(u) > currDist(v) + weight(edge(vu)) {
                currDist(u) = currDist(v) + weight(edge(vu));
                predecessor(u) = v;
                如果 u 不属于 toBeChecked ，就把它添加进去;

            }    //end if

        }    //end for
    }    //end while

}    //end algorithm