1回答
我似乎有点难以理解贪婪的策略是如何工作的，以及Dijkstra的算法如何跟踪最短路径。这里是Dijkstra算法的伪代码，供参考 InitalizeSingleSource(G, s) Q = G.V，我的答案是s->t->y->x，长度为9，我假设伪码中的"S“是最短路径，而来自minQ的每个minQ都添加到了路径中。Dijkstra的算法使用贪婪策略，我认为贪婪策略总是选择<
浏览 2提问于2018-12-03得票数 0
回答已采纳
2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。input A
set B[i, j] = 0 for i = 1 to n: b_ij = min(b_ij, b_
浏览 8提问于2021-02-22得票数 1
2回答
我目前正在实施一个导航系统，用于欧洲的路线选择。到目前为止，我已经实现了最短路径(Dijkstra和A*)。这是最简单的部分，现在我需要一些最快路径的算法。它必须是快速可靠的。我在寻找更精确的算法。地图本身包含各种数据，如道路质量、限速、红绿灯位置等，我想使用它。
有没有好的算法来解决这个问题呢？或者至少是A*的一个好的修改。
浏览 1提问于2010-09-30得票数 3
回答已采纳
1回答
我目前正在尝试理解Yen的k条最短路径算法。我以原始论文和维基百科文章为基础，但仍然不明白为什么k> 2是正确的。事实上，我甚至不明白为什么它适用于以下例子：例如，让我们考虑从A到D的3条最短路径，即A -> B -> C -> D(长度3)、A -> B -> F -> D(长度4)和A -> B ->根据我对该算法的了解，正确地计算了2条最短路径。然而，第三条最短路径是与顶点B处的第二条最短路径的偏差，而路
浏览 0提问于2016-05-01得票数 2
回答已采纳
3回答
我知道我们可以很容易地在DAG中找到最短/最便宜的方法，但如果我们的资金有限呢？所以想象下下一种情况：我们有8个money.The算法可以找到-10+-3= -13的最短路径，但它将花费12美元，但我们只有8美元，所以这不是一个选择。有没有可以用来解决这个问题的算法？
浏览 1提问于2015-07-07得票数 4
1回答
我知道有很多最短路径算法，但我想问一问是否可以做任何修改，使一些算法，比如a*或Dijkstra选择最短路径，但不需要对角移动。
向下和左右是允许的移动。
浏览 0提问于2016-10-15得票数 0
回答已采纳
2回答
我正在尝试理解A*，统一成本和贪婪搜索算法是如何工作的。我知道探索节点的方式在所有三种算法中都会发生变化(贪婪将基于启发式值进行探索，A*基于启发式加距离，均匀基于距离)。我想知道，对于给定的源和目的地，是否所有3种算法都应该提供最短路径(只需探索不同数量的城市？)或者他们能提供一条不同的路径。我最困惑的是实现部分-如果你将节点存储在队列中，那么当你打算探索目标节点时，你将拥有它的最短路径，但是如果你有路径队列(这个队列现在是基于启发式+距离排序的)，那么你可能不会总是获得最短路
浏览 4提问于2016-10-04得票数 1
我有一个家庭作业，我要找出两个城市之间最便宜的机票，考虑到中途停留。DijkstraAlgorithm(weighted simple digraph, vertex first)
我很难理解的是--尤其是在看整个伪代码的时候--为什么它只接受一个顶点作为参数我需要找到两个顶点之间最便宜的机票(最短路径)。为什么算法只需要一个？
浏览 4提问于2011-12-05得票数 2
回答已采纳
1回答
寻找最短周期
、、
基本上，我需要在一个图中有一个覆盖所有顶点并返回到源的最短路径。只要是最短路径，任何顶点的重复都是可以的。
我的算法从源开始。我运行dijkstra算法来找到最短路径。然后我选择最小的加权未达顶点，并再次运行dijkstra作为所选顶点作为源，并继续运行，直到所有顶点都完成。然后，从最后一个顶点再次使用dijkstra找到返回原始源的最短路径。
浏览 0提问于2012-10-30得票数 0
在目标c中有一种简单的方法来应用像Dijkstra最短路径算法这样的东西，以便知道这两个变量点中的最短路径？真正的问题是我有一个图像，上面有一系列的位置和所有这些位置的坐标。现在我需要用户选择这个位置中的两个，并选择两个位置之间的最短路径。
浏览 1提问于2012-05-24得票数 3
回答已采纳
关于地下爆炸的最新消息让我对以下问题感到好奇。假设我们有一个加权的无向图，其中的节点有时会被删除。问题是在这样的删除之后快速地重新计算所有节点对之间的最短路径。只需对进行简单修改，我们就可以计算出所有对之间的最短路径。这些路径可以存储在一个表中，其中shortest[i][j]包含i和j之间最短路径上的下一个节点的索引(如果没有路径，则为NULL值)。该算法建表时间为O(n³)，每次查询shortest(i,j)耗时为O(1)。不幸的是，我们应该在每次删除后重新运行此算法</em
浏览 1提问于2010-03-29得票数 4
4回答
“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别，哪种算法是图中最短路径的最佳选择？我需要计算网络中所有对之间的最短路径，并将结果保存到一个数组中，如下所示：A 0 10 15 5 20
B 10
浏览 20提问于2009-12-04得票数 27
回答已采纳
2回答
我想知道是否有一种算法可以在图中找到最短路径。
假设我有一个图，从一个顶点到另一个顶点有一对路径。这些路径中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法会找到最短路径，但他们只“选择”一条。
浏览 1提问于2010-08-09得票数 1
回答已采纳
我知道，如果算法达到负循环，算法就不会终止，如果路径包含一个距离大于0的循环，那么它就不是最短路径。
我的问题是，如果存在一个循环距离为0的最短路径会发生什么，算法会将该循环包含在最短路径中吗？你会说所有的最短路径都是非循环的吗？
浏览 13提问于2017-06-20得票数 0
2回答
我正在寻找一种算法，我肯定已经研究过了，但我对图论还不太熟悉，甚至不知道要搜索的正确术语。在抽象中，我正在寻找一种算法来确定可达顶点x1、x2、xn和某个起始点之间的路由集，当每条边都有一个权重，而每条路径只能有给定的最大总重量x时。如果我能找到在这段时间内可以到达的最远点，那么我将使用凸包算法来确定区域(这对我的用例来说已经足够了)。
那么，我的问题是，我如何找到这些终点？我的第一个直觉是使用Dijkstra的算法，并在我“消耗”了一定的“预算”时间后停止，从每个路段的预算中减去；但是当算法</
浏览 3提问于2015-07-09得票数 3
回答已采纳
2回答
我有一个有向无环图，需要找到有资源约束的最短路径。我的限制是所选择的路径必须具有最小数量的设置资源消耗。我已经找到了相当多关于这个主题的文献，我认为提供了一个很好的概述。然而，我正在努力理解它，并找到一个能够实现的简明算法(我正在使用Python，但是任何清晰的算法想法都会很好)。
我知道这个问题是NP完全的，因此我
浏览 1提问于2011-12-31得票数 3
回答已采纳
3回答
我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢，但我想不出来。根据维基百科，Johnson算法使用Bellman Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法查找最短路径。但贝尔曼·福特算法也是一种寻找最短路径的算法。为什么我们不使用从贝尔曼·福特算法得到的最短路径呢？
浏览 0提问于2011-03-16得票数 4
回答已采纳
1回答
我试图在加权多向图中找到一条最短路径(最便宜)，其中顶点是城市，边缘是城市之间的路线，权重是价格。我使用Dijkstra来获得最便宜的路径，我只是将每个边的权重设置为公司的价格。即使对C.然后，如果该算法访问C所拥有的节点，则将C所拥有的所有其他边的权重设置为0。否则，该算法将继续正常运行。问题是，Dijkstras算法总是优先考虑即时
浏览 1提问于2021-12-21得票数 3
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
