单源最短路径

引言

在最短路径问题中，我们给定一个加权有向图 G = (V, E)，其中权重函数w: E → R将边映射到实值权重。路径 p = (v₀,v₁,..... v_k) 的权重是其组成边的权重总和

我们通过 δ(u,v) = min (w (p): u→v) 来定义从 u 到 v 的最短路径权重，如果存在从 u 到 v 的路径，则为 δ(u,v)= ∞，否则。

然后，将从顶点 s 到顶点 t 的最短路径定义为权重为 w (p) = δ(s,t) 的任何路径 p。

广度优先搜索算法是适用于无权图的最短路径算法，也就是说，在其中可以认为每条边都具有单位权重的图。

在单源最短路径问题中，我们给定一个图 G = (V, E)，我们希望找到从给定的源顶点 s ∈ V 到每个顶点 v ∈ V 的最短路径。

变体

最短路径问题存在一些变体。

• 单目的地最短路径问题：找到从每个顶点 v 到给定目的地顶点 t 的最短路径。通过转换图中每条边的方向，我们可以将此问题缩短为单源问题。
• 单对最短路径问题：找到从给定顶点 u 和 v 的最短路径。如果我们确定以源顶点 u 为源的单源问题，我们也可以阐明这个问题。此外，对于此问题，尚无算法在最坏情况下运行速度快于最佳单源算法。
• 所有对最短路径问题：找到从 u 到 v 的最短路径，对于每对顶点 u 和 v。从每个顶点运行一次单源算法可以阐明这个问题；但通常可以更快地解决，并且其结构本身就很有趣。

最短路径：存在性

如果从 s 到 v 的某些路径包含负成本循环，则不存在最短路径。否则，存在一个简单的最短 s - v。