引言

最短路径算法是图算法中比较重要的组成部分，在《算法导论》中有比较详细的阐述和证明。很长时间没在看过图算法的内容，在接触到增强学习后，复习了下A*算法，故对最短路径算法进行一下简单的总结，A*算法将会另外开一篇文章。Dijkstra和Floyd算法是最为经典的两个针对无向图进行最短路径求取的算法，本文先对这两个算法进行回顾和总结。

Dijkstra算法

Dijkstra算法在解决最短路径算法时有一定的局限性，要求图中不能存在负边权重（具体的证明可参考《算法导论》）。个人看来Dijkstra算法应该属于贪心算法的部分，但某些参考书籍把它归入到了动态规划的范围。当然我们不会对这个问题深究，看自己证明好理解吧。Dijkstra是从源点出发，一次求取到其余所有点的最短路径。这也称为单源最短路径。
<script type="math/tex" id="MathJax-Element-20710">\qquad</script>算法的大致是先从源点S<script type="math/tex" id="MathJax-Element-20711">S</script>出发，选取距离源点距离最短的点V1<script type="math/tex" id="MathJax-Element-20712">V1</script>，然后比较从S<script type="math/tex" id="MathJax-Element-20713">S</script>到V2<script type="math/tex" id="MathJax-Element-20714">V2</script>的距离ds,v2<script type="math/tex" id="MathJax-Element-20715">d_{s,v2}</script>和以V1<script type="math/tex" id="MathJax-Element-20716">V1</script>为过渡点再到V2<script type="math/tex" id="MathJax-Element-20717">V2</script>的距离ds,v1,v2<script type="math/tex" id="MathJax-Element-20718">d_{s,v1,v2}</script>大小。如果前者大于后者，则更新S<script type="math/tex" id="MathJax-Element-20719">S</script>到V2<script type="math/tex" id="MathJax-Element-20720">V2</script>的距离为ds,v1,v2<script type="math/tex" id="MathJax-Element-20721">d_{s,v1,v2}</script>，否则不改变。然后依次类推计算后面的点，最终得出从S<script type="math/tex" id="MathJax-Element-20722">S</script>到所有点的最短路径。上面说得可能比较抽象，不要急，这只是一个大致阐述，后面你会很清楚的。经过上面的阐述，也看出了一个事实，每次选取的是最小的点，这是贪心的思想，但在求取另外的点时又利用到了之前求取的点，这便又和动态规划相似。现在，我们以一个具体的例子来说明算法的具体求解过程。
如上图，现在我们要求从源点A<script type="math/tex" id="MathJax-Element-20723">A</script>开始求取图中其它点的最短路径。具体过程是：
（1）. 将A<script type="math/tex" id="MathJax-Element-20724">A</script>放入最后的结果中Ret<script type="math/tex" id="MathJax-Element-20725">Ret</script>；
（2）. 选取与A<script type="math/tex" id="MathJax-Element-20726">A</script>距离最短的点，显然是C<script type="math/tex" id="MathJax-Element-20727">C</script>，更新A<script type="math/tex" id="MathJax-Element-20728">A</script>经过C<script type="math/tex" id="MathJax-Element-20729">C</script>到其它与C<script type="math/tex" id="MathJax-Element-20730">C</script>有直接连接的点的距离，更新的规则上面已经说过，以B<script type="math/tex" id="MathJax-Element-20731">B</script>为例，A−>B<script type="math/tex" id="MathJax-Element-20732">A->B</script>的距离大于A−>C−>B<script type="math/tex" id="MathJax-Element-20733">A->C->B</script>的距离，所以更新A−>B<script type="math/tex" id="MathJax-Element-20734">A->B</script>的距离为5。同时，A<script type="math/tex" id="MathJax-Element-20735">A</script>到DE<script type="math/tex" id="MathJax-Element-20736">DE</script>初始是无穷大（图的存储约定），所以更新A<script type="math/tex" id="MathJax-Element-20737">A</script>到DEF<script type="math/tex" id="MathJax-Element-20738">DEF</script>的距离分别为{6、7}，并加入最后的结果中，Ret={A,C}<script type="math/tex" id="MathJax-Element-20739">Ret=\{A,C\}</script>；
（3）. 由于C<script type="math/tex" id="MathJax-Element-20740">C</script>已经被选取，在下一次选择距离A<script type="math/tex" id="MathJax-Element-20741">A</script>最短的点时就不再考虑C<script type="math/tex" id="MathJax-Element-20742">C</script>，那么这次选择显然就是B<script type="math/tex" id="MathJax-Element-20743">B</script>，比较还没加入Ret<script type="math/tex" id="MathJax-Element-20744">Ret</script>且和B<script type="math/tex" id="MathJax-Element-20745">B</script>直接连接的点（C、D）<script type="math/tex" id="MathJax-Element-20746">（C、D）</script>，更新规则和上面一样，最后将B<script type="math/tex" id="MathJax-Element-20747">B</script>加入到Ret<script type="math/tex" id="MathJax-Element-20748">Ret</script>中，这时Ret={A,C,B}<script type="math/tex" id="MathJax-Element-20749">Ret=\{A,C,B\}</script>;
（4）. 以此类推，选择D<script type="math/tex" id="MathJax-Element-20750">D</script>并更新和D<script type="math/tex" id="MathJax-Element-20751">D</script>直接相连的点，并加入到Ret<script type="math/tex" id="MathJax-Element-20752">Ret</script>中。
最后Ret={A,C,B,D,E,F}<script type="math/tex" id="MathJax-Element-20753">Ret=\{A,C,B,D,E,F\}</script>,这便是源点A<script type="math/tex" id="MathJax-Element-20754">A</script>到图中所有点的最短路径，例如求A−>E<script type="math/tex" id="MathJax-Element-20755">A->E</script>的最短路径便是A−C−B−D−E<script type="math/tex" id="MathJax-Element-20756">A-C-B-D-E</script>。简易代码如下（因为手头电脑问题，并没有运行检查正确性）：

const int MAXINT = INT_MAX;        //图中不直接连接的点的权重定义
const int MAXNUM = 6;               //图中的节点数目
int dst[MAXNUM];                    //存放源点到其它点的距离
int prev[MAXNUM];                   //存放路径

int G[MAXNUM][MAXNUM];              //图的邻接矩阵

void Dijstra(int v0)
{
    bool used[MAXNUM];                 // 判断图中节点时候已经被加入最后的结果中，初始为false
    int node_num = MAXNUM;
    for(int i = 1; i<=n; i++)
    {
        dst[i] = G[v0][i];          //从邻接矩阵中获取距离信息
        used[i] = false;
        if( MAXINT == dst[i] )
            prev[i] = -1;
        else
            prev[i] = v0;           // 设置源点直接连接的点的前驱为源点
    }

    dst[v0] = 0;                    // 源点到源点的距离设置为0
    used[v0] = true;                   //标记源点已经被加入最后的结果中

    for(int i = 2; i <= n; i++){
        int mindst = MAXINT;
        int u = v0;
        for(int j = 1; j <= n; j++)          // 选取目前距离矩阵中与源点最短距离的点
        {
            if( (!used[j]) && dst[j] < mindst){
                u = j;
                mindst = dst[j];

            }

            used[u] = true;                    //将该点加入到最后结果中
            for(int j = 1; j <= n; ++j)
            {
                if( (!used[j]) && G[u][j] < MAXINT)
                {
                    if(dst[u]+G[u][j] < dst[j])
                    {
                        dst[j] = dst[u]+G[u][j];    // 更新距离
                        pre[j] = u;                 // 设置前驱
                    }
                }
            }
        }
    }
}

Floyd算法

Dijkstra算法是解决单源最短路径算法，当需要解决图中任意两点的最短路径时，Dijkstra则需要多次计算，而且，当图中存在负的边权重时，Dijkstra则显得无能为力。Floyd算法的提出很好的解决了这一问题，能一次求出任意两点的最短路径，并且边权重可正可负。
<script type="math/tex" id="MathJax-Element-21331">\qquad</script>Floyd算法的思想是从两点最短路径的可能性思考的，两点之间的最短路径无非有如下几个情况：
（1）. 两点直接到达的距离最短。
（2）. 两点之间通过1个或者1个以上节点连接到达的距离最短。
所以，如果是第一种情况，则可以在邻接矩阵中直接获取。如果是第二种情况，则需要依次判断以每个点为中间点连接起点和终点的最短距离。如果需要中间点的个数大于1，则将问题继续划分为其它终点和起点的问题。例如求AB间的最短距离，对于中间点有C，那么则需要判断distance(A,B)<script type="math/tex" id="MathJax-Element-21332">distance(A,B)</script>与distance(A,C)+distance(C,B)<script type="math/tex" id="MathJax-Element-21333">distance(A,C)+distance(C,B)</script>的大小，如果还有其它点，则间distance(A,C)<script type="math/tex" id="MathJax-Element-21334">distance(A,C)</script>和distance(C,B)<script type="math/tex" id="MathJax-Element-21335">distance(C,B)</script>按照这种方式继续划分下去，很显然，Floyd算法其实就是一种自顶而低的动态规划。我们先给出代码：

void getGraphicData(){//获取数据  
    ifstream in("data");  
    in>>vertexnum>>edgenum;  //获取节点数和边数
    int from,to;  
    double w;  
    // 初始化邻接矩阵和路径矩阵
    while(in>>from>>to>>w){  
        weight[from][to] = w;  
        path[from][to] = from;
        weight[from][from] = 0; 
        path[from][from] = from;  
        weight[to][to] = 0;  
        path[to][to] = to;  
    }  
}  
void floyd(){  
    for(int k = 0;k < vertexnum;k++)  // 中间点变量
        for(int i= 0;i < vertexnum;i++)  // 起点变量
            for(int j = 0;j < vertexnum;j++){  //终点变量
                    weight[i][j] = min(weight[i][j], weight[i][k] + weight[k][j]);  
                    path[i][j] = path[k][j];  
                }  
            }  
}  
void displaypath(int source,int dest){  // 求取路径
    stack<int> shortpath;  
    int temp = dest;  
    while(temp != source){  
        shortpath.push(temp);  
        temp = path[source][temp];  
    }  
    shortpath.push(source);  
    cout<<"short distance:"<<weight[source][dest]<<endl<<"path:";  
    while(!shortpath.empty()){  
        cout<<shortpath.top()<<" ";  
        shortpath.pop();  
    }  
}  

结合下图：

(1). 初始化工作无非就是对图的邻接矩阵就行初始化，直接连接的边为常数权重，非直接连接的边初始化为无穷大，路径矩阵则是对点的前驱进行计算。
(2). 首先确定中间点k<script type="math/tex" id="MathJax-Element-23703">k</script>，例如k=x<script type="math/tex" id="MathJax-Element-23704">k=x</script>，计算[u,v]<script type="math/tex" id="MathJax-Element-23705">[u,v]</script>的最短距离,显然：

<script type="math/tex; mode=display" id="MathJax-Element-23706">{dist(u,v)=min(dist(u,x)+dist(x,v),dist(u,v))}</script> dist(u,v)<script type="math/tex" id="MathJax-Element-23707">dist(u,v)</script>是邻接矩阵的值（无穷大），所以[u,v]<script type="math/tex" id="MathJax-Element-23708">[u,v]</script>的最短距离目前应该是[u−>x−>v]<script type="math/tex" id="MathJax-Element-23709">[u->x->v]</script>。当需要加入更多中间点时，则按照这种方式继续划分下去。在划分过程中比较路径大小，最后得出最小值。
(3). 最后是确立路径，也就是起点和终点之间的中间点。
Floyd算法在实现时有一点需要注意，就是中间点的循环(这里时k)必须在外层，如果放在内层时，有的路径权重不会改变，这会对最后的结果产生错误，说起来比较难懂，可以手动模拟一下，就会发现这个问题。

小结

Dijkstra算法适合于单点的路径就算，而当需要任意两点间的最短路径时，Floyd算法比V<script type="math/tex" id="MathJax-Element-23710">V</script>次Dijkstra算法效率要高，并且当图中存在负权重时，Dijkstra则无能为力。除了这两种算法外，SPFA对于稀疏图的效率比较高，但计算任意两点的最短路径时，Floyd算法的效率依然高于V<script type="math/tex" id="MathJax-Element-23711">V</script>次SPFA计算效率。