图论:单源最短路径

本文概述

介绍

在最短路径问题中, 我们得到了一个加权有向图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。

单源最短路径
微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?