本文概述
- 介绍
- 变体
- 最短路径:存在
文章图片
如果存在从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的最短路径。从每个顶点运行一次单一源算法可以阐明此问题;但是通常可以更快地解决它, 其结构本身就是令人感兴趣的。
文章图片
推荐阅读
- 图论(负权重边)
- DNS问题故障排除(使用nslookup、dig和host等命令)
- MySQL性能调优和优化技巧(如何优化数据库())
- NoSQL数据库类型和流行的NoSQL数据库合集介绍
- 如何将NSX-V迁移到NSX-T(详细分步指南)
- TLS与SSL差异比较(有什么区别(哪个更好?))
- Telnet与SSH差异比较(SSH与Telnet有何不同())
- 如何使用MegaCLI设置硬件RAID(分步指南)
- Rsync命令用法指南(Linux中的20个有用示例)