---

前言

本文讲解几种求解单源最短路径问题的算法，Bellman-Ford算法解决的是一般情况下的单源最短路径问题。在一般情况下，边的权重可以为负值。Bellman-Ford算法非常的简单，并且还能够侦测是否存在从源结点可以到达的权重为负值的环路。接着给出一种在有向无环图中计算单源最短路径的线性时间的算法。Dijkstra算法的时间复杂度低于Bellman-Ford算法，但却要求边的权重为非负值。最后本文会描述如何使用Bellman-Ford算法来解决线性规划中的一种特殊情况。

---

一、最短路径相关概念介绍

如上所述是最短路径的定义，及最短路径权重的定义。边上的权重除了表示距离也可以代表非距离的度量单位，如时间、成本、罚款、损失，或者任何其他可以随路径长度的增加而线性积累的数量以及我们想要最小化的数量。

单源最短路径问题：给定一个图G=（V，E)，我们希望找到从给定源结点s∈V到每个结点υ∈V的最短路径。

单源最短路径算法还可用于求解如下的一些变体问题：

如对于单目的最短路问题，我们可以使用之前讲解的图转置操作转置后，再将终点视为起点，再将其作为算法输入求解。

上述引理说明最短路径具有最优子结构性质，可使用剪切—黏贴法对其加以证明。这是一个使用动态规划算法与贪心算法的重要指标。

下面说明一些影响最短路径问题的因素。

负权重的边:

当图中存在s可达的负权重的环路时，会导致某些节点（环上所有节点及从环可达的节点）到原点s没有最短路径的定义，因为可以绕此环无限次从而得到一个更短的路径。

环路:

最短路径中是否可以包含环路？

如上所述，最短路径中不可以存在负权重环路，否则会导致最短路径无定义。而对于权重>0的环路来说，如果最短路径中存在这样的环路，那么我们始终可以删除这一环路得到一个更短路径。对于权重=0的环路，我们可以删除这一环路得到一个等价的最短路径。

因此，我们可以得出结论，最短路径中不包含环路，及它是简单路径，而对于图G(V,E)，其简单路径至多包含|V|个节点，因此最短路径至多包含|V-1|条边。

最短路径的表示:
之前再讲BFS时，说过前驱子图的概念，在单源最短路算法中同样具有这一概念：

也就是说前驱子图是算法结束后，由图中所有父节点不为空的节点，及它们与父节点的边的边集所构成的子图。

可以证明算法最终生成的前驱子图是一颗最短路径树。当算法生成这棵树，我们就可以使用之前讲的打印路径的算法来打印任意一点到s的最短路径。

需要说明的是最短路径可能是不唯一的，因此生成的最短路径树也不一定是唯一的。

松弛操作:

/// <summary>
/// 初始化图
/// </summary>
/// <param name="g"></param>
/// <param name="s"></param>
public static void InitSignalSource(Graph g,Node s)
{
    foreach (var v in g.nodes)
    {
        v.Distance = int.MaxValue;
        v.Parent = null;
    }
    s.Distance = 0;
}

/// <summary>
/// 松弛操作，若u作为v到s路径上的节点可使得v到s距离更小则将u作为v的父节点
/// </summary>
/// <param name="e"></param>
/// <returns>若权重发生变化则返回true，否则返回false</returns>
public static bool Relax(Edge e)
{
    var u = e.n1;
    var v = e.n2;
    if (v.Distance>_Add(u.Distance,e.Weight))
    {
        v.Distance = _Add(u.Distance, e.Weight);
        v.Parent = u;
        return true;
    }
    return false;

    int _Add(int a,int b)
    {
        if (b>0&&a>=int.MaxValue-b)
        {
            return int.MaxValue;
        }
        return a + b;
    }
}

注意这里可能存在计算溢出的问题，并且不考虑存在负权重环路的情况（所以权重不可能是无穷小），因为u.Distance可能为无穷大值，我们定义无穷大值+一个有限值=无穷大，所以需要重写加法逻辑。

也许你可能感到疑惑，这明明是一个估计值从大到小逼近实际值的过程，不应该是”收紧“操作吗？关于这点书中是这样解释的：

本文的每个算法都将调用算法INITIALIZE-SINGLE-SOURCE，然后重复对边进行松弛。而且，松弛是唯一导致最短路径估计和前驱结点发生变化的操作。本文所讨论的所有算法之间的不同之处是对每条边进行松弛的次数和松弛边的次序有所不同。Dijkstra算法和用于有向无环图的最短路径算法对每条边仅松弛一次。Bellman-Ford算法则对每条边松弛|V|一1次。

下面给出一些重要的性质，这些性质在后续证明算法正确性时会使用到，而关于这些性质本身的证明，过程过于繁琐，本文不给出证明过程，若有兴趣，可查阅《算法导论》一书。

二、Bellman-Ford算法

 /// <summary>
 /// BellmanFord算法可输入存在负权重边的图，并能检测负权重环的存在。否则生成图的最小路径树
 /// </summary>
 /// <param name="g"></param>
 /// <param name="s"></param>
 /// <returns>若存在从原点s可达的负权重的环，则返回false</returns>
 public static bool BellmanFord(Graph g,Node s)
 {
     InitSignalSource(g,s);

     for (int i = 1; i < g.nodes.Length; i++)
     {
         foreach (var v in g.nodes)
         {
             foreach (var adje in v.AdjTable)
             {
                 Relax(adje);
             }
         }
     }

     //最后再松弛一遍检测负权重环的存在
     foreach (var v in g.nodes)
     {
         foreach (var adje in v.AdjTable)
         {
             if (Relax(adje))
             {
                 return false;
             }
         }
     }
     return true;
 }

下图描述了一个该算法的工作实例：

对应的测试代码如下：

            var v = new string[] { "s", "t", "x", "y", "z" };
            var g = new Graph(v, true);

            //添加边
            g.AddEdge("s", "t", 6);
            g.AddEdge("s", "y", 7);
            g.AddEdge("t", "x", 5);
            g.AddEdge("x", "t", -2);
            g.AddEdge("t", "y", 8);
            g.AddEdge("z", "x", 7);
            g.AddEdge("t", "z", -4);
            g.AddEdge("y", "x", -3);
            g.AddEdge("z", "s", 2);
            g.AddEdge("y", "z", 9);

            var s = g.FindNode("s");
            var z = g.FindNode("z");
            //调用BellmanFord算法生成最小路径树
            Graph.BellmanFord(g, g.FindNode("s"));
            //打印路径
            g.PrintPath(s, z, z);

可以通过分析得知，此算法复杂度为O（VE）。

如何理解该算法执行过程？

我们可以这样理解，之前我们说过最短路径是简单路径，对于图G(V,E)有V个节点，其最长的简单路径至多有|V-1|条边，注意这正是算法中的循环次数。该算法正确性依赖于上述的路径松弛性质。每次循环都对所有的边松弛一次，那么必然包含对路径p（假设为最长路径）上第i条边（循环次数）的松弛，根据此性质，最终路径p的权重会是最短路径权重。

上述引理可使用松弛性质证明。

证明该算法正确性我们分两种情况，一种是图中不含s可达的负权重环，在此种情况下若v∈V到s可达，根据上述引理以证明u.d=δ(s,u),而对于u不可达的情况由非路径性质可知该等式依然满足，再结合前驱子图性质我们可得出结论， G_π 是一颗最短路径树。

而对于包含s可达的负权重环的情况，在算法最后检测环的过程中，环上的节点会使得松弛操作始终可行，从而返回false。

三、有向无环图中的单源最短路径问题

拓扑排序与之前的代码稍有不同：

/// <summary>
/// 拓扑排序(邻接表使用adjtable)
/// </summary>
/// <param name="g">待排序的图</param>
/// <param name="allowBack">是否允许存在后向边(有环)</param>
/// <returns>返回拓扑序的链表</returns>
public static LinkedList<Node> TopoLogicSortByAdjTable(Graph g, bool allowBack = false)
{
    if (!g.IsDirect)
    {
        Console.WriteLine("只可对有向图进行拓扑排序");
        return null;
    }
    LinkedList<Node> list = new LinkedList<Node>();
    //全局时间计数器
    int time = 0;
    //初始化所有节点
    foreach (var v in g.nodes)
    {
        v.color = NodeColor.White;
        v.Parent = null;
        v.d = int.MinValue;
        v.f = int.MinValue;
    }
    //遍历所有节点，得到多颗深度优先树
    foreach (var v in g.nodes)
    {
        if (v.color == NodeColor.White)
        {
            try
            {
                _DFS(v);
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                //return null;
            }
        }
    }
    return list;
    void _DFS(Node u)
    {
        u.d = ++time;

        u.color = NodeColor.Gray;

        foreach (var adje in u.AdjTable)
        {
            var adjv = adje.GetOther(u);
            //如果节点尚未探索
            if (adjv.color == NodeColor.White)
            {
                adjv.Parent = u;
                _DFS(adjv);
            }
            if (adjv.color == NodeColor.Gray && !allowBack)
            {
                throw new Exception($"检测出有向图存在环，后向边为{u.Name}-->{adjv.Name}");
            }
        }
        u.color = NodeColor.Black;

        u.f = ++time;

        list.AddFirst(u);
    }
}

仅仅是对新的邻接表进行适配，其他逻辑不变。

DAG求最短路径问题算法完整代码如下：

/// <summary>
/// 有向无环图（DAG）的一种线性时间的求最短路径的算法, 权重可为负，但不能有负权重环
/// </summary>
/// <param name="g"></param>
/// <param name="s"></param>
public static void DAGShortestPaths(Graph g,Node s)
{
    InitSignalSource(g, s);

    var list=TopoLogicSortByAdjTable(g);

    foreach (var v in list)
    {
        Console.WriteLine(v.Name);
        foreach (var adje in v.AdjTable)
        {
            Relax(adje);
        }
    }
}

该算法复杂度为θ(V+E)。

下图是算法的一个运行实例：

测试代码如下：

            var v = new string[] { "r", "s", "t", "x", "y", "z" };
            var g = new Graph(v, true);

            //添加边
            g.AddEdge("r", "s", 5);
            g.AddEdge("r", "t", 3);
            g.AddEdge("s", "x", 6);
            g.AddEdge("s", "t", 2);
            g.AddEdge("t", "x", 7);
            g.AddEdge("t", "y", 4);
            g.AddEdge("t", "z", 2);
            g.AddEdge("x", "z", 1);
            g.AddEdge("x", "y", -1);
            g.AddEdge("y", "z", -2);

            var s = g.FindNode("s");
            var z = g.FindNode("z");
            //调用BellmanFord算法生成最小路径树
            Graph.DAGShortestPaths(g, g.FindNode("s"));
            //打印路径
            g.PrintPath(s, z, z);

该算法思路为，将DAG进行一次拓扑排序，因为DAG无环可以排出一个次序使得对于边A–>B，A始终位于B之前。在按照排序好的顺序进行节点邻接边的松弛，从一开始便按照路径松弛性质的顺序进行松弛操作，进行到最后自然会得到一条最短路径。

证明思路同上，根据路径松弛性质与非路径性质证明算法进行到最后，所有节点到u.d=δ(s,u)，在结合前驱子图性质证明前驱子图G_π即为最短路径树。

四、Dijkstra算法

/// <summary>
/// Dijkstra算法假设所有边权重非负，输入一个有向图，生成最短路径树
/// </summary>
/// <param name="g"></param>
/// <param name="s"></param>
public static void Dijkstra(Graph g, Node s)
{
    InitSignalSource(g,s);
    //创建优先队列
    var q = new Tree.Heap<Node>(g.nodes.Length);
    
    foreach (var v in g.nodes)
    {
        q.PushNode(v);
    }
    while (q.Count>0)
    {
        var u = q.PopNode();

        foreach (var adje in u.AdjTable)
        {
            var adjv = adje.GetOther(u);

            if (Relax(adje))
            {
                q.UpdateNode(adjv);
            }
        }
    }
}

下图为该算法的一个运行实例：

测试代码如下：

var v = new string[] { "s", "t", "x", "y", "z" };
var g = new Graph(v, true);

//添加边
g.AddEdge("s", "t", 10);
g.AddEdge("s", "y", 5);
g.AddEdge("t", "x", 1);
g.AddEdge("y", "t", 3);
g.AddEdge("t", "y", 2);
g.AddEdge("z", "x", 6);
g.AddEdge("x", "z", 4);
g.AddEdge("y", "x", 9);
g.AddEdge("z", "s", 7);
g.AddEdge("y", "z", 2);

var s = g.FindNode("s");
var x = g.FindNode("x");
//调用BellmanFord算法生成最小路径树
Graph.Dijkstra(g, g.FindNode("s"));
//打印路径
g.PrintPath(s, x, x);

该算法是贪心算法，它每次都选择集合V-S中距离集合S最近的那个节点，我们也知道贪心算法求出的解不一定为最优解，但是可以证明对于此算法确实可以求出最短路径。

书中使用如下的循环不变式对上述定理进行证明：

关于循环不变式三段论的证明过程较为繁琐，这里不再展示其详细过程。

Dijkstra算法的复杂度与最小优先队列的实现细节管理较大，观察代码我们发现，其中涉及优先队列的入队、更新、出队三种操作，这其中对于每个节点入队出队操作只会发生一次，而更新操作与|E|的大小相关。

如果我们选择数组来实现优先队列，那么入队、更新操作可以在O(1)时间内完成，出队操作则与元素个数相关（O(V)），其总的运行时间为O(V²+E)=O(V²)。

如果我们选用二叉堆来实现优先队列，对于上述三种操作都为O(lgV)，因此其总运行时间为O((V+E) lgV)，若图为稀疏图，即|E|较小，那么更新操作执行较少，此时其性能相较于数组实现有所改善。

事实上，我们可以使用斐波那契堆进一步改善运行时间，从历史的角度上看，斐波那契堆提出的动机就是因为人们观察到Dijkstra算法调用的DECREASE-KEY操作通常比EXTRACT-MIN操作更多，因此，任何能够将DECREASE-KEY操作的摊还代价降低到o（lgV)而又不增加EXTRACT-MIN操作的摊还代价的方法都将产生比二叉堆的渐近性能更优的实现。

我们观察到Dijkstra算法与BFS算法有些相似，两者相似之处在于集合S对应BFS中的黑色节点集合（即广度遍历完成的节点），且最终都会生成一颗树，通过该树可以获取节点到原点的路径即距离信息。它们的不同之处在于BFS使用普通队列存储灰色节点（边权重为单位权重，因此对于同级的灰色节点弹出顺序不影响最终结果），而Dijkstra使用优先队列存储这些节点（同级别的边需要按照权重有序弹出）。

如果你看过上篇文章中Prim算法的代码，你会发现，这两者也是高度相似。这两者的区别主要在于，Prim算法中的操作类似于松弛操作但非松弛，他不会与中间节点u的权重相加而是直接比较边的权重。这样的改动造成算法执行过程的不同，对于Prim算法，可将其生成的局部的MST理解为一个大的节点，每次选择距离这个大节点最近的那个节点，而Dijkstra算法的执行效果则是每次选择距离当前节点u最近的那个节点（它考虑了节点到达s的距离u.d）。

五、差分约束和最短路径

差分约束问题是线性规划问题的一种特例，线性规划问题描述如下：

概括的解释就是在由线性不等式定义的可行域内，寻找目标函数的最优值

有时候，我们并不关注目标函数，而仅仅是希望找到一个可行解，即找到任何满足Ax≤b的向量x，或者判断不存在可行解。差分约束问题正是这样的一类问题

下图是差分约束问题的一个示例：

差分约束问题不关注目标函数，只关注解向量x满足所有的线性不等式（约束）。

上述引理证明也很简单，我们将不等式中每个x_i加任意一个常量d，所得的不等式当然依旧满足。

这里将差分约束问题转换为图论问题需要一定的抽象思维，其关键的桥接点在于三角不等式性质。对此不等式稍加变形我们得到v.d-u.d≤w(u,v)，发现其形式正好对应差分约束中的一组约束，而所有的边的权重对应b向量，所有的节点对应了解向量x。有如下定理：

可以通过反证法证明此定理正确性。这里我非正式的说明一下其大致原理，如果图中不存在负权重环路，且所有节点到s可达，那么对于图中任意节点满足三角不等式性质，从而可推导为原问题约束的形式。如果存在负权重环路，由于没有最短路径定义三角不等式自然也不再成立。

在此示例中由于不存在从s可达的负权重环路，可使用Bellman-Ford算法对该问题求解。

总结

本文讲解了三种单源最短路径算法，其中Bellman-Ford算法求解一般情况下的最短路径问题，DAG最短路径算法在求解DAG的最短路径问题时可以达到线性运行时间，其也可接收负权重图，Dijkstra求解假设所有权重非负的有向图最短路径问题，并给出了这些算法在某些情况下的特殊应用。