如果2个图节点之间的间接路径比直接路径短，Dijkstras算法可以检测到吗？
沙拉小子
Dijkstras 算法根据起始节点和中间节点之间的边权重假设最近的邻居。重复此过程直到到达目标节点。
如果起始节点和中间节点之间的最短路径是通过其他几个中间节点的间接路由怎么办？
叶夫根尼·格特森
如果起始节点和中间节点之间的最短路径是通过其他几个中间节点的间接路由怎么办？
在尝试找到最短路径时，通常会穿越多个节点。如果没有多个可能的路径，那么您为什么需要 Dijkstra？
想象下图：
为了更好地理解，假设算法从顺时针方向开始，START从1节点开始。它将发现START -> 1 -> 6 -> END成本为 7。然后逆时针走，发现START -> 3 -> 5 -> 8 -> 9 -> END成本为 5。然后算法将逆时针路径标记为从START到的最短路径END。
现在假设我们有以下图表：
该算法将发现START -> 1 -> 9成本为 5（顺时针）和START -> 3 -> 5 -> 8 -> 9成本为 4（逆时针）。因此，算法会将逆时针路径标记为从START到的最短路径END，其成本为 5。接下来，算法将尝试找到另一条经过 的路径（如果可能的话）START -> 1 -> 6 -> END。它将发现这条路径的成本为 4，并且会将这条路径标记为从START到的最短路径END。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
是否有图算法可以找到节点之间的最短路径，合并节点以避免？
- 2
算法检测形成路径的节点的顺序
- 3
在 NEO4j 中查找两个节点之间的间接路径
- 4
查找两个节点之间的路径，即使中间节点丢失也无法查询图
- 5
使用BFS查找2个节点之间的最短路径
- 6
使用BFS查找2个节点之间的最短路径
- 7
Dijkstra的“单源最短路径”算法可以检测图中的无限循环吗？
- 8
两个不相交集之间的路径（路径算法）
- 9
查找使两个节点之间的最大权重最小的路径的算法
- 10
给定节点之间的最短距离矩阵，如何确定2个节点之间的路径？
- 11
生成类路径时检测到一个循环
- 12
无向图，检查节点之间是否存在路径
- 13
在无向加权图中打印2个节点之间的所有最小路径
- 14
如果我使用OpenVPN，我的提供商可以检测到p2p流量吗
- 15
两个Trie节点之间的最短路径
- 16
如何查找两个节点之间的路径的名称
- 17
MySQL-递归两个节点之间的树路径
- 18
OrientDB两个节点之间的所有路径
- 19
如何使用Leaflet在两个节点之间绘制路径
- 20
可以直接导航到路径路径，但不能通过单击链接导航吗？
- 21
遍历节点之间的最佳路径
- 22
遍历节点之间的最佳路径
- 23
在Prolog中定义图：边和路径，查找两个顶点之间是否存在路径
- 24
在图算法中找到最短路径
- 25
在项目的构建路径中检测到一个周期... eclipse
- 26
蓝牙无法检测到设备，但hcitool可以检测到吗？
- 27
Neo4j查询最短路径卡住（不工作），如果我在图节点中有2way关系并且节点相互关联
- 28
如何检查2D阵列中两个单元之间的直接路径是否被给定单元阻塞？
- 29
HashLocationStrategy 和 Location Strategy Import.Angular 2 & Typescript 后未检测到路径
我来说两句