最短路算法最优_最短路径最优算法_最经典的最短路径算法 - 腾讯云开发者社区

、

如何在中修改Dijkstra算法来计算两个节点之间的最短第二条和第三条路径？

浏览 0提问于2017-01-25得票数 0

1回答

什么是最优子结构的直觉？

、

整体最优解包含两个相关子问题的最优解。谢谢

浏览 5提问于2012-10-24得票数 2

1回答

可以使用A*搜索非网格图吗？

、、、

我知道A*是寻找最短路径的最优算法，但我不知道任何启发式算法是如何在非格图上工作的？这让我想知道A*实际上是否能够用于无向或有向图。如果A*能够做到这一点，那么什么样的启发式方法可以使用呢？如果A*不是，那么目前在有向或无向非格图上计算最短路径的最快算法是什么？如果需要更多的信息，请发表评论。

浏览 0提问于2014-12-08得票数 2

回答已采纳

1回答

Bellman算法的中间最优性，是正确的吗？

、、

Bellman算法是著名的求解任意连通图G(V，E)的单源最短路径问题(SSSPP)的算法。该算法的基本实现版本，例如：及其，在使用所有边的并行松弛时，根据我的理解，意味着一个有趣的副产品，我称之为“中间最优性属性”(可能对一些应用程序(如)非常有用)如下：上述属性正确

浏览 4提问于2014-09-12得票数 0

回答已采纳

1回答

最宽路径与最长路径问题的基本区别

、、

最宽路径和最长路径问题有什么区别？更具体地说，为什么前者可以通过找到最大生成树来解决，而后者却不能。

浏览 2提问于2014-08-12得票数 1

回答已采纳

2回答

今天，我阅读了关于算法的介绍，该算法在加权有向图中询问通过两个顶点的最长简单路径是什么。作者用一个很好的例子说明了动态规划对于最长路径问题是失败的，因为没有一个很好的最优结构总是伴随着一个最优子结构。那么每条“最长路径”都会自动成为最短路径，如果在最短路径中没有循环，那么对应的最长路径中就不应该有任何循环。因此，使用一个相当常见的技巧，我们可以将最长路径问题转化为最短路径问题。阅读书中提供的伪代码，最短路径的算法似乎并不禁止使用负数，

浏览 3提问于2015-02-23得票数 0

1回答

图分层与DP

、、、

图分层是处理具有一定限制的最短路径的一种常用技术。下面是关于这种技术的描述：。所以，只是想知道，这个技术是否和做DP一样，但是只是有一个不同的记忆结构？

浏览 4提问于2017-04-29得票数 0

回答已采纳

2回答

从单个源到所有其他节点在生成树中寻找最短路径的最佳算法

、、、、

如果我知道给定的图实际上是一棵生成树，即每一对顶点之间只有一条路径，那么如何才能找到从每个顶点到每个顶点的最短路径？我想要最理想的解决方案。我知道Dijkstra的算法，但它非常复杂。考虑到它是一棵生成树，那么它的最佳和最优解是什么？请原谅我的过度解释。

浏览 6提问于2014-12-11得票数 0

回答已采纳

1回答

多源多目标最短路径问题

、、、

我试图找出从所有源节点到任何一个目标节点的最短路径的最优方法，从而在加权图中得到最小的权重。所有节点都是源节点或目标节点。所以图我们有一个图，A，B，C作为源节点，D，E，F作为目标节点。A，B，C必须找到任何一个恰好有最短路径的目标节点的最短路径。简单的解决办法是使用Dijkstra算法或类似的方法，首先找到从A到D的最短路径，然后从A到E等，然后比较每条最短路径的最终权重，看看哪条路径实际上最短。我想知道是否有更有效的解决办法。

浏览 4提问于2022-11-05得票数 0

3回答

一种在迷宫中搜索多目标星形算法的改进

、、、

如果我已经在迷宫中完成了A*算法的实现，以便找到通向单个目标的最短路径(就像pacman游戏一样)，那么我应该如何改进当前的启发式算法(曼哈顿到目标的距离+从一开始到现在的旅行成本)，以便我的算法能够支持迷宫中的多个目标基本上，我想找到通过迷宫中所有目标的最短路径。为了确保路径是最优的，假设我们忽略了问题中的一致性，启发式函数需要是可接受的。我知道这就像旅行推销员问题，但现在我只处理相对少量的数据，所以我想继续使用A start算法。欢迎任何想法。谢谢!

浏览 10提问于2016-09-21得票数 0

回答已采纳

1回答