图论：单源最短路径

本文概述

在最短路径问题中, 我们得到了一个加权有向图G =（V, E）, 权重函数为w：E→R将边映射到实值权重。路径p的权重=（v0, v1, ….. vk）是其组成边权重的总和：

如果存在从u到v的路径, 并且δ（u, v）=∞, 我们定义最短的-从u到v的路径权重为δ（u, v）= min（w（p）：u→v） , 除此以外。

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

广度优先搜索算法是适用于未加权图的最短路径算法, 也就是说, 其中每个边都可以视为具有单位权重的图。

在单源最短路径问题中, 给定一个图G =（V, E）, 我们想要找到从给定源顶点s∈V到每个顶点v∈V的最短路径。

最短路径问题有一些变体。

单目标最短路径问题：找到从每个顶点v到给定目标顶点t的最短路径。通过移动图中每个边的方向, 我们可以将此问题简化为单源问题。
单对最短路径问题：找到给定顶点u和v的从u到v的最短路径。如果我们确定源顶点为u的单源问题, 我们还将对此问题进行说明。此外, 在最坏的情况下, 没有一个算法能比最佳的单源算法渐近地运行。
全对最短路径问题：为u和v的每对顶点找到从u到v的最短路径。从每个顶点运行一次单一源算法可以阐明此问题；但是通常可以更快地解决它, 其结构本身就是令人感兴趣的。

如果从s到v的某个路径包含负成本周期, 则不存在最短路径。否则, 存在最简单的s-v。