算法入门：如何计算图的最短路径？

最短路径的定义是什么？

最短路径是权重最小的路径p；
路径定义：p=，其中当时，有(,)E；
路径权重：w(p)=；

加上权重的数学表示

1. 边权重图：G(V,E,W)，W是作用在边上生成实数的函数，即从W(E)开始的路径->R
2. 顶点到自身：()表示从()到()，权重为0
3. 两个顶点之间的最短路径：
   

的E 和 V 之间的关系 E=O()。假设有向图有两个顶点 v1 和 v2，它们之间只有四种连接情况，以此类推。

为什么会有负权重？

例如，社交网络上的点赞可以视为正权重，点赞可以视为负权重。

负体重铅会带来什么问题？

如果存在权重为负的边，则每次循环都会减少原来的权重值，导致出现任意可用权重值都可以获得的现象。比如路径p=的权重是4，但是路径p=的权重是3

最短的大致思路是什么路径算法？

d(v)表示源点s到当前节点v的路径权重，表示v在当前最佳路径上的前一个节点。这样就可以重构出整个最短路径

对于没有负权重的环

1. 初始化 d[v] = ,=NIL, dSpread收缩=0
2. 选择边 ( u ,v) 以某种方式执行Relax操作， go 会完成从源顶点到所选顶点更新当前路径值的过程，以及从所选顶点的前一个节点开始的

Relax(u,v,w):
    select edge(u,v):
        if d[v]>d[u]+w(u,v):
            d[v]=d[u]+w(u,v)
            PI[v]=u
    until all edges have d[v] <= d[u]+w(u,v)
复制代码

relax操作，返回值？​​小于(s,v)？

假设通过归纳我们有 d[u] (s,u)。已知表示从s到v的最短路径，并且每个顶点u到v以及源点s到u的最短路径必须大于或等于，即

.根据前面的假设，一定有。这说明中间过程任意阶段产生的结果d[v]都不会小于(s,v)

最短路径算法的一般思想。问题一：错误的选择导致复杂度为指数级别

构建一个具有以下结构的图

边的权重按照分布。以图中 6 个点为例，如果显示的所有边（,）均为，并减少到 1

，假设源点为，则选择的路径初始化如下，即可求出从源点到任意点的路径长度。

此时，Relax(,)的边缘会将路径长度从更新为到13

，然后Relax(, 侧面），从到的路径长度更新为10

由于新的到的路径长度较短，因此（ , ) 缩短为 11

此时，有可能首先选择执行 Relax 的边是 (,)，然后是 (,) ) 缩短为 12

再次放松边 (,)，则 (,) 的路径缩短为 11

对于有 n 个顶点的情况： 首先放松(, ), 使 d[] 减去 1

，然后放松(,), 使 d[ ] 减 2

，然后 Relax(,) 和 (,) 使 d[] 减少 1

，然后进入 Relax (,出) ，将 d[] 减少 1

可以在放松时找到。当边（、）的权重为1时，顶点d（）减1；当Relax边(,)的权重为2时，顶点d()减2，即同时按照1,2,4,...的方式进行权重,,,总共需要减少d()次数为1+2+4+...+=,即例如执行次数是指数的

最短路径算法的总体思路问题2：负权重环

如果源点在经过目的节点的路径上，经过一个循环就会导致权重减少，而这个算法不会结束。

如何获得有向无环图（DAG）中从单个源点到给定点的最短路径？

DAG 表示只有无环且存在负边权

1. 对 DAG 进行拓扑排序，保证从 u 到 v 的路径一定是 u 在 v 之前
2. 找到源顶点，从左起向右，按照DAG排列的顺序，对每个经过的顶点进行Relax操作，得到源顶点到所有顶点的最短路径。

假设排序后的拓扑图如下所示。对于初始化，最短路径是从每个源点到每个节点。距离考虑为

第一步从源点向下移动，找到所有的边，并对边进行Relax操作。

源点完成后，按照拓扑排列顺序从左向右移动。因为Relax只改变小写字母，所以只改变最后两节该点的路径值已更新

继续执行向右松弛

继续执行向右松弛

至此，执行完成。可以看到从源点到所有节点的最短路径，从左到右分别是 ,0,2,6,5,3

如果图中有环路，但是经过了这个循环不会导致权重减少，那么如何计算最短路径呢？

Dijkstra算法的伪代码算法使用如下：

Dijkstra(G,w,s): //G是图，w是权值，s是源点
    Initialize(G,s) // 初始化，设置dSpread收缩=0,其它都是无穷，以及PI
    S <- {}    //已知最短路径的点的集合
    Q <- V[G]  //需要被处理的顶点，可以看做是一个最小优先级队列，根据d()值进行排序
    while Q is not empty: //只要还有没处理的节点
        u <- Extract-Min(Q) //从节点中找出一个最小的路径权重的节点，并从Q中移除
        S <- S U {u} //将找到的节点并到S中
        for each vertex v belong to Adj
            Relax(u,v,w) //对边的d()值进行更新
复制代码

示例如下：选择A作为源点

1. 进行初始化，A到其他节点的距离为，即：S={}, Q={ A(0),B(),C(),D(),E()};
2. 获取队列中的最小值，当前为 A 本身。此时S={A(0)}，则进行Relax操作，即发现A能到达的顶点为B、C，更新后队列中的值为Q={B( 10), C(3), D (),E()};
3. 获取队列中的最小值，当前为C, S= {A(0),C(3 )}，在选中的C上放松，C可以到达的节点为B、D、E。对应的队列更新为：Q={B(7),D(11), E(5)};
4. 获取队列的最小值，当前为E。 S={A(0),C(3),E(5)}，在选中的E上运行Relax，能到达E的节点为D，由于大于现有的D值，所以不会更新。 Q= {B(7),D(11)};
5. 获取队列的最小值，当前为B。此时S={A(0),C(3),E(5),B(7) }，B只能到达D，B到D得到的值为9，应该更小是 。更新Q={D(9)}
6. 以获得队列的最小值。现在是D，现在S={{A(0),C(3),E(5),B(7),D(9)}，这就结束了。

括号中的值代表路径距离

Dijkstra算法的时间复杂度

所有耗时操作包括：

• 将所有顶点插入优先级队列，其中;
• 需要从优先级队列中获取一个最小值，需要；
• 放松控制会降低边缘的d值，这就需要；优先级队列的实现方式不同，持续时间也不同

1. 使用数组。提取最小值的成本：，Relax减少d值并服务队列中的所有元素，那么使用最小堆的时间为=
2. 。提取最小值的成本：，减少了key的成本，队列中所有元素都服务完毕，则时间为
3. 使用斐波那契堆，提取最小值的成本： ，降低钥匙成本。费用，可以实现

使用Dijkstra最直观的感受是：下图为例：

假设绿色点是源点。如果用这个长度的绳子连接每个节点，就拿一个绿色的球，从上到下挂起来。直线之和是从源点到任意点的最短距离。例如，绿色为源点，到其他点的最短距离为7、12、18、22（颜色为紫色、蓝色、黄色和红色）

为什么Dijkstra可以解决负权重问题？

Dikstra 不看已经处理过的节点，而只处理还没有见过的节点。如果处理的节点都是最小值且不存在负权循环，则路径不会改变。小情况。有关更多信息，请参阅：https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm/6799344#6799344

如果从源节点到目标节点的路径上存在环路，并且它会导致体重。 Reduce，如何处理最短路径问题？

使用贝尔曼-福特算法。

Bellman-Ford(G,w,s):
    Initialuze(G,s)
    for i=1 to |V|-1:
        for each edge(u,v) belong to E:
            Relax(u,v,w)
    for each edge (u,v) belong to E:
        if d[v]>d[u]+w(u,v)
            report negative cycle exist
复制代码

最后，Bellman-Ford提供的是，如果不存在权重为负的环，则可以返回最短路径（d[v]=），否则只会找到权重为负的环的存在检测权重

耗时分析

两个for循环，分别是V和E，所以时间复杂度是O(VE)

为什么Bellman-Ford算法可以在没有负权重循环的情况下计算出最小路径？

你只需证明，如果不存在负权循环，经过贝尔曼-福特，d[v]=。

取最短路径 p=，其中 为 s，=v。如果不存在负权环，则p是一条简单路径，即k|V|-1。

这不可能是一个正环，也就是说，每次经过这个环重量都会增加。如果是，那么这不是最短路径

执行第一个循环时，取边 ( , ) 进行 RELAX，则有 \delta(s, ) = d []
第二个周期输出边沿 (, )。放松，那么我们有 \delta(s,)=d[]
然后经过 k 个周期我们有 \delta(s,)=d[]，就是这样|V|-1 次循环后，已计算出从源顶点到每个顶点的最短路径

简单路径：表示除起点和终点外，其他顶点不重复。 。对于简单路径 p=，如果 k>=|V|，则路径上的顶点总数为 |V|+1，但在实际只有|V|顶点，那么一定有重复边，它重复了非起点和终点，这意味着它不是一条简单的路径

为什么Bellman-Ford算法可以检测到负权循环？

如果|V|-1轮后仍有一条边可以放松，那么当前从s到v的最短路径就不是一条简单路径，因为所有节点都已经看过了，必然存在于这一条上times 双节点，即存在权重为负的环路

如果一条路径上存在环路且所有权重值为负权重，那么使用 Bellman-Ford 算法是否可以得到最长路径？

否，因为 Bellman-Ford 仅在存在负权重环时抛出异常，并且不计算路径。这其实是一个N-P问题，即所花费的时间处于指数级别或更高

类似，是的，不经过负权环，计算最短路径并不容易

作者：Reptile
来源：掘金队