加权有向图的单源最短路径问题是图论中的经典问题。单源最短路径问题指的是从一个节点出发，计算到图中其它所有节点的最短路径的问题。Dijkstra算法可以有效解决这个问题（权值不能为负数）。
对于加权有向图中的节点v，它的任意一个前继邻居节点u到v的路径(u,v)是一个独立的路径，不依赖任何其它前继邻居节点u'到v的路径(u',v)。
我们在这里对图做一个扩展，增加一种特殊的节点，称为汇合节点。从起始节点到汇合节点的路径是汇合节点的一个或多个前继邻居节点到汇合节点的路径的组合，组合时对各个分支距离进行加法和乘法运算。
简单点讲，要想走到汇合节点，必须先同时走到它的一个或多个前继邻居节点。至于具体要走过哪几个前继邻居节点，要根据具体的条件要求来判断。
这种情况在生活中经常会遇到，一件事情有多个可选的前置条件，想要完成这件事情，必须先完成一个或多个前置条件。
以图一为例：
节点d是汇合节点，这里的汇合条件是从起始节点a到d节点的路径是其所有前继相邻节点的路径的和。也就是说要想走到d，必须先同时走到b和c，然后才能计算从a到d的距离|a->d|=|a->b|+|b->d|+|a->c|+|c->d|。
对于扩展后的带有汇合节点的加权有向图的单源最短路径问题应该如何解决？Dijkstra算法是否依然有效？我们来分析一下这个问题。
Dijkstra算法的原理
Dijkstra算法的特点是从起始节点开始向外层层扩展，直到所有节点都被访问到。
Dijkstra算法将节点分为两组，一个是已求出最短路径的节点的集合S（初始时只有起始节点），另一个是未确定最短路径的节点的集合U。每次新扩展一个距离最短的节点，更新与其相邻节点的距离（只在相邻节点当前的最短路径大于经过扩展节点的路径时更新）。当所有边的权值都为正时，不会存在一个距离更短的没扩展过的节点，所以这个节点的距离不会再被改变，将其加入到S中。因此，在将节点加入到S的过程中，总是保持从起始节点到S中任何节点的最短距离都不大于从起始节点到U中任何节点的最短距离。从起始节点开始，直至集合U中的所有节点都转移到了集合S中。
以图二为例：
假设a为起始节点。从a出发，有b和c两个相邻节点。此时需要从|ab|和|ac|中选择一个距离最短的路径。如果|ac|<|ab|，因为权值为正，所以|ac|<|ab|+|bc|一定成立，因此c一定是到a的路径最短的节点，将c加入到集合S中。反之，如果|ab|>|ac|，所以b是到a的距离最短的节点，将b加入到集合S中，此时从a到c的最短路径还要通过比较|ab|+|bc|与|ac|的大小来决定。
汇合节点引入的问题
从Dijkstra算法的原理可以看到，节点向外扩展的过程中，每次都要从集合U中选择一个距离最短的节点。汇合节点的问题在于，在扩展节点时，无法立即计算出汇合节点的最短路径。因为汇合节点要求对它的所有前继相邻节点进行组合计算，而在扩展时难以保证汇合节点的所有前继相邻节点都已计算出最短路径。
如果不能计算出汇合节点的最短路径，那么就无法按照Dijkstra算法的要求选择出距离最短的节点。此时应该如何处理？
以图一为例，从a出发先到达c。更新c的相邻节点时，无法计算汇合节点d的距离。这种情况下应该如何处理？
对汇合节点的分析
我们首先来看节点向外扩展的过程，为什么每次都要从U集合中选择距离最短的节点？从Dijkstra算法的原理可以知道，因为需要保证不会存在距离更短的节点，从而保证被选中节点的当前路径就是从起始节点到它的最短路径，所以被选中节点可以放到集合S中。
对于图中的任意一个节点，如果它的相邻节点存在汇合节点，有两种情况：
- 汇合节点是路径最短的节点
- 非汇合节点是路径最短的节点
对于情况2，非汇合节点会被选择作为距离最短的节点，符合Dijkstra算法的要求，不存在问题。
对于情况1，我们深入分析一下。
对于非汇合节点u和它的相邻节点v，我们用λu、λv表示u和v的最短路径距离，λ|uv|表示u和v之间的距离，可以知道：
λv=λu+λ|uv|
=> λv>λu, λv>λ|uv|
对于汇合节点v和它的前继相邻节点u1,u2...uN，λv=C(λu1+λ|u1v|,λu2+λ|u2v|...,λuN+λ|uNv|)，其中C为汇合节点v的最短路径计算函数。可以知道对于汇合节点v的任意一个位于v的最短路径中的前继相邻节点u：
λv>=∑i(λui+λ|uiv|)(i=1~N)
=> λv>=λu+λ|uv|
=> λv>λu, λv>λ|uv|
对于普通节点u、u的普通相邻节点v以及u的汇合相邻节点w，如果w路径更短，则有λw<λv，假设组成w的最短路径的任意前继相邻节点为x（x可能包括u），根据上面内容可以知道:
λw<λv
λw>=λx+λ|xw|, λv=λu+λ|uv|
=> λx+λ|xw|<λu+λ|uv|
=> λx<λu+λ|uv|
=> λx<λv
如果x=u，那么λ|uw|<λ|uv|，说明uw之间的距离小于uv之间的距离。
如果x≠u, λx<λu，则x先于u被访问，因而w先于v更新。
如果x≠u, λu<λx，则u先于x被访问，但是根据λx<λv，x会先于v被访问。
根据上面的推导，如果在节点u的相邻节点中汇合节点w的距离最短，那么组成汇合节点w的最短路径的任意前继相邻节点x都会优先于u的其它任意相邻节点v被访问。这也就意味着汇合节点w能够先于v被访问。
调整Dijkstra算法
根据上面的推导，对于带有汇合节点的加权有向图的单源最短路径问题仍然可以使用Dijkstra算法，只需做一个局部的调整：在向外扩展节点时，如果其相邻节点中有汇合节点，则更新其对应的分支路径的距离，但是直至汇合节点满足了C函数可以计算完全的距离时才参与后续的最短距离节点的选择。
示例
以图三为例：
其中e为汇合节点，其C函数为所有前置相邻节点构成的路径的总和。
以a为起始节点，其计算步骤如下：
-
初始化
节点 a b c d e f g 前序访问节点 Φ Φ Φ Φ Φ Φ Φ 距离 +∞ +∞ +∞ +∞ +∞ +∞ +∞ 访问顺序 -
访问a节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a Φ Φ Φ Φ 距离 0 5 6 +∞ +∞ +∞ +∞ 访问顺序 1 可以发现，b是距离a路径最短的未访问节点。
-
访问b节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a b b? Φ Φ 距离 0 5 6 15 6? +∞ +∞ 访问顺序 1 2 可以发现，b的邻居节点中存在汇合节点e，我们只更新通过b到e的路径的距离，因为还有一个前继节点形成的路径暂时不确定，所以无法计算e的距离，因此e不参与下一轮的选择。
排除e之后，c是距离a路径最短的未访问节点。 -
访问c节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a b b+c c Φ 距离 0 5 6 15 6+8=14 11 +∞ 访问顺序 1 2 3 更新c到e的路径的距离，就可以计算a到e的距离了。
可以发现，f是距离a路径最短的未访问节点。 -
访问f节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a b b+c c f 距离 0 5 6 15 6+8=14 11 16 访问顺序 1 2 3 4 可以发现，e是距离a路径最短的未访问节点。
-
访问e节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a b b+c c e 距离 0 5 6 15 6+8=14 11 15 访问顺序 1 2 3 5 4 因为从e到g的距离比从f到e更近，因此更新g。
可以发现，d是距离a路径最短的未访问节点。 -
访问d节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a b b+c c e 距离 0 5 6 15 6+8=14 11 15 访问顺序 1 2 3 6 5 4 因为从d到g的距离比从e到g更远，因此不用更新g。
可以发现，g是距离a路径最短的未访问节点。 -
访问g节点并更新其相邻节点的距离
节点 a b c d e f g 前序访问节点 Φ a a b b+c c e 距离 0 5 6 15 6+8=14 11 15 访问顺序 1 2 3 6 5 4 7 至此，图中所有节点都已被访问。
我们可以发现，从a到g的最短路径是经过汇合节点e形成的路径，其距离为15。
