Graph Algorithms

介绍 Dijkstra 算法前先介绍最短路径树（SPT，Shortest-Path Tree）定义：一个图和它的一个指定的源点（即出发顶点）s，s的最短路径树是指包含 s 以及从 s 可达的所有顶点，它们形成一棵以 s 为根的有向树，其中 每条树路径为图中的最短路径。

显然，Dijkstra 算法就是寻找最短路径树（SPT）的算法。

Dijkstra’s algorithm 的基本思想描述如下： 开始时，将源点放在 SPT 上，然后，一次一条边地生成 SPT，所取的下一条边总是从源点到非 SPT 上顶点的最短路径。换句话说，Dijkstra 算法就是哪个顶点离源点的距离近，就先添加到 SPT 中。 Dijkstra 算法是一种贪心算法。

Dijkstra 算法的具体步骤如下：
(1)、首先给出发顶点标上永久性标号 0，然后给每个与出发顶点直接相连的结点标上一个临时标号，标号值为连接出发顶点和该结点线路的权值。给其它没有和出发顶点相连的结点的临时标号为∞。
(2)、选择具有最小临时标号的结点（这就是贪心算法的策略），将该结点的临时标号改为永久性标号。
(3)、假设结点 i 是刚获得永久性标号的结点，搜索每个与结点 i 直接相连的结点 j，在“结点 j 目前的临时标号”和“结点 i 的永久性标号+边(i,j)的权值”两者间取一个较小的值对结点 j 的临时标号进行更新。
(4)、重复步骤(2)~(3)，直到所有结点都具有永久性标号。永久性标号值就是出发顶点到该结点的最短距离。

说明：由于每次要选择具有最小临时标号的结点，所以在实现 Dijkstra 算法时往往要用到优先队列。

Dijkstra 算法的伪代码如下：

// Pseudocode (excerpted from wikipedia)
function Dijkstra(Graph, source):

    create vertex set Q

    for each vertex v in Graph:             // Initialization
        dist[v] ← INFINITY                  // Unknown distance from source to v
        prev[v] ← UNDEFINED                 // Previous node in optimal path from source
        add v to Q                          // All nodes initially in Q (unvisited nodes)

    dist[source] ← 0                        // Distance from source to source

    while Q is not empty:
        u ← vertex in Q with min dist[u]    // Source node will be selected first
        remove u from Q

        for each neighbor v of u:           // where v is still in Q.
            alt ← dist[u] + length(u, v)
            if alt < dist[v]:               // A shorter path to v has been found
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

下图中线上所标注的数字为相邻结点之间的距离（即权值），设结点 1 为源点，求源点到其他各点的最短路径。

注 1：黄色点表示“最小临时标号”的点，绿色点表示还未分析过的点，红色点表示永久性标号的点。
注 2：下面过程中，“选择”对应前面介绍算法中的步骤(2)，“更新”对应步骤(3)。

算法结束后，可以通过回溯前驱结点找到最短路径树（SPT）。

参考：
http://wenku.baidu.com/view/8837010aba1aa8114431d9ec.html
http://www.utdallas.edu/~dzdu/cs6363/lect06.ppt

Dijkstra 算法的简单实现如下：

//Dijkstra算法的简单实现
//其中图用邻接矩阵表示
#include<iostream>
using std::cout;
using std::endl;

#define NoEdge 100000   //用NoEdge表示不邻接的结点间的权值。NoEdge的值远大于所有边的权值。
#define N  6            //图中的结点总数。

//功能，求从s点开发到各个结点的最短路径。
//w表示图的（带权）邻接矩阵。
//在数组d[]中返回结点到源点的最短距离。
//在数组p[]中返回最短路径树(SPT)中结点的前驱结点。
//w、s为输入参数，d、p为输出参数。
void Dijkstra(int w[][N], int s, int d[], int p[])
{
    int known[N] = {0};
    int i;
    for (i = 0; i < N; i++) {//初始化d[]和p[]。
        d[i] = w[s][i];      //给d[]赋初值，注意有向图中w[s][i]和w[i][s]是不同的。
        if (d[i] <NoEdge)
            p[i] = s;        //把和源点s相连的结点的前驱结点标记为s。
        else
            p[i] = -1;       //把和源点s不相连的结点的前驱结点标记为-1。
    }

    known[s] = 1;            //known[i]=1时表示结点i已经加入到最短路径树(SPT)中，即它的最短路径已经确定。

    //开始主循环，每次求得s到某个结点k的最短路径，并设置known[k]=1。
    for (i = 1; i < N; i++) { //只要更新N-1次即可。i只是用来控制更新次数，在循环体中没有用到。
        int t = NoEdge;
        int k = s;
        for (int j = 0; j < N; j++) { //每次在最短路径树(SPT)外的结点中找离s最近的结点，标记为k。
            if((!known[j]) && (d[j] < t)) {
                t = d[j];
                k = j;
            }
        }
        known[k] = 1;

        for (int j = 0; j < N; j++) {  //更新当前最短路径及距离
            if((!known[j]) && (w[k][j] < NoEdge) && (d[j] > d[k] + w[k][j])) {
                d[j] = d[k] + w[k][j];
                p[j] = k;
            }
        }
    }
}

//测试Dijkstra程序
int main()
{
    int w[N][N] = {
        {0,2,4,NoEdge,NoEdge,NoEdge},
        {NoEdge,0,1,4,2,NoEdge},
        {NoEdge,NoEdge,0,NoEdge,3,NoEdge},
        {NoEdge,NoEdge,NoEdge,0,NoEdge,2},
        {NoEdge,NoEdge,NoEdge,3,0,2},
        {NoEdge,NoEdge,NoEdge,NoEdge,NoEdge,0}
    };
    int d[N];
    int p[N];

    Dijkstra(w,0,d,p);

    cout<<"Vertex:  "<<"Shortest Path:  "<<"Predecessor Vertex:"<<endl;
    for (int i = 0; i < N; i++) {
        cout<<i+1<<"        "<<d[i]<<"               "<<p[i]+1<<endl; //+1仅仅是为了把起始结点号从0变为1。
    }
    return 0;
}

说明 1：上面的实现不是高效的，可以通过用“优先队列”代替数组 d 来提高效率。
说明 2：对于稀疏图用邻接矩阵是很低效的，应该使用邻接表。

上面程序中使用的测试数据来自上节介绍的实例。运行程序，得到下面输出：

Vertex:  Shortest Path:  Predecessor Vertex:
1        0               1
2        2               1
3        3               2
4        6               2
5        4               2
6        6               5

得到上面的输出结果容易得到对应的最短路径树，即图 21 。

开放最短路径优先（Open Shortest Path First, OSPF）算法是 Dijkstra 算法在网络路由中的一个具体实现。

Dijkstra 算法不适应有权值为负数的情况。

SPFA 全称 Shortest Path Faster Algorithm ，用于求单源最短路径（可以认为 SPFA 是对 Bellman-Ford 算法的优化）。
SPFA 是段凡丁（西南交通大学软件学院副院长）于 1994 年发表的。

有时，给定的图存在负权边，这时 Dijkstra 等算法便没有了用武之地，而 Bellman-Ford 算法的复杂度又过高，SPFA 算法便派上用场。
该算法在 NOIP（全国青少年信息学奥林匹克联赛）和 ACM-ICPC（ACM 国际大学生程序设计竞赛）竞赛中受到广泛的关注和学习，赢得了强烈的反响和好评。

Warshall 算法用来计算有向图的传递闭包（Transitive Closure）。

参考：《算法设计与分析基础，第 2 版，Anany Levitin 著》8.2 节。

Floyd-Warshall 算法常常简称 Floyd 算法。
Floyd 算法几乎和 Warshall 算法完全一样，不同之处在于，它不使用逻辑运算来跟踪路径的存在，而检查每条边对应的路径来判断该边是否为新的更短路径的一部分。
为了方便起见，我们把最短路径的长度记录在 $n$ 阶矩阵 $D$ 中，这个矩阵称为路径矩阵(Distance Matrix)。如图 25 所示。