在最大二部匹配的Hopcroft-Karp算法中，为什么我们总是在广度优先搜索中寻找最短的增广路径？是不是因为广度优先搜索总是找到最短的路径？我只是搞不懂为什么增强路径是最短的，这很重要。
浏览 2提问于2013-05-15得票数 0
回答已采纳
那么，如果两条最短的增广路径的长度是2，那么第二个过滤器是什么？然而，这两条路径的长度都是2。那么这个算法是否会扩展并说“选择具有最大/最小流量的路径”？
浏览 6提问于2016-07-15得票数 0
回答已采纳
在我们运行FF算法并得到残差grpah Gf和min-cut (S，T)之后，这是我的方法。(1)使用BFS找出到u的部分增广路径s和从v到t的所有部分增广路径。如果这两条部分增广路径都存在。找到从交叉边到t的最短路径，这个距离+1(交叉边)将是我们的最
浏览 3提问于2017-12-10得票数 0
这是一个一般性的算法问题。我想在无向图上运行一些最短路径算法，其中边和顶点都有关联的成本。大多数最短路径搜索算法都没有考虑顶点成本。有什么方法可以弥补这个问题吗？
浏览 2提问于2013-01-01得票数 3
回答已采纳
我将介绍OSRM实现；他们实现了路由算法CH和MLD。我想知道它使用这些算法的动机是什么。更重要的是，在这两种算法中，我们不能动态地改变边权重。
浏览 0提问于2019-04-29得票数 0
scipy.optimize.linear_sum_assignment的时间/空间复杂度是多少？它也被称为匈牙利问题。
浏览 13提问于2022-02-15得票数 1
回答已采纳
1回答
用堆栈求加权图的最短路径
、、、
我已经搜索了一些算法，但它的接缝似乎是一些不可能的事情，对我来说，它们是不可能的。事实上，使用是可能的，但不幸的是，我只能使用堆栈(而不是矩阵)。我也寻找，但我无法得到与我的问题的关系。
显然，我的目标是从一个点到另一个点得到所有最短路径。正如我前面提到的，我将用向量字符串从我的堆栈输出解决方案。我想我必须访问每个节点，而我最害怕的是在搜索过程中被堆叠成一个循环，甚至失去跟踪。如果Dijkstra的算法适用于这里，我将非常感谢你们中的任何人来指导我，我非常感谢任何帮助、建议、想法，甚至是在搜索过程中不要被堆叠在一起或松
浏览 0提问于2013-11-15得票数 2
回答已采纳
我知道，如果算法达到负循环，算法就不会终止，如果路径包含一个距离大于0的循环，那么它就不是最短路径。
我的问题是，如果存在一个循环距离为0的最短路径会发生什么，算法会将该循环包含在最短路径中吗？你会说所有的最短路径都是非循环的吗？
浏览 13提问于2017-06-20得票数 0
1回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
1回答
我目前正在尝试理解Yen的k条最短路径算法。我以原始论文和维基百科文章为基础，但仍然不明白为什么k> 2是正确的。事实上，我甚至不明白为什么它适用于以下例子：例如，让我们考虑从A到D的3条最短路径，即A -> B -> C -> D(长度3)、A -> B -> F -> D(长度4)和A -> B ->根据我对该算法的了解，正确地计算了2条最短路径。然而，第三条最短
浏览 0提问于2016-05-01得票数 2
回答已采纳
因此，dijkstra算法是搜索加权(无负)连通图最短路径的最佳算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。
问题:我的理解正确吗？它也能用来寻找某些顶点的最短路径吗？例如，图有A，B，C，D，E，F，G，H，I，J，K，我们只对A，B；C，K的最短路感兴趣，我们可能只需要一次就能找到两条路吗？
浏览 2提问于2018-03-12得票数 1
1回答
非赋权图中的最大流
、、、
最大流问题通常采用edmond-karp算法来解决，该算法建立残差图，并利用BFS来寻找增广路径。
但最大流问题通常是针对赋权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。
浏览 4提问于2017-02-22得票数 4
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
我想写一个算法，在有向图和无向图中找到两个特定顶点-源和目标-之间的最短路径。
我知道dijkstra的算法，它用来寻找所有的最短路径图。但是，您是否会修改此算法以仅查找两个顶点之间的最短路径？
浏览 31提问于2018-01-11得票数 0
1回答
我正在使用Dijkstra算法解决最短路径问题。我遇到了麻烦，因为算法应该提供最短路径，但在运行该算法后，我手动获得了一条最短路径。这只是这个算法的副产品吗？我尝试生成的路径来自-> z这是我应用算法得到的路径，在我访问的每个顶点上进行最短距离的跳跃：
2 4 2 2 1 2 1 1
浏览 3提问于2012-04-21得票数 2
回答已采纳
我最近一直在研究所有对最短路径算法，比如弗洛伊德-瓦赫尔和约翰逊的算法，我注意到这些算法产生了正确的解，即使一个图包含负权边(但不包含负权环)。作为比较，Dijkstra的算法(它是单源最短路径)不适用于负重边。是什么使全对最短路径算法在负权重的情况下工作？
浏览 9提问于2014-04-06得票数 6
回答已采纳
1回答
我需要一个algorithm(k, s)
算法找出从一个节点到另一个节点的最短路径，而不是
浏览 2提问于2014-10-20得票数 1
我最近正在学习图形算法，在我的大学里，我们被教导说，Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对最短路径)。然而，我不明白这个算法是如何实现的，我试图通过观看YouTube视频和查找维基百科中的定义来理解它……我无法找到描述该算法的资源，其结果将是所有对最短路径表，但只能“从一个节点到所有其他节点对Bellman算法进行调整以实现所有对最短路径表，还是我的大学讲师在这方面完全错
浏览 8提问于2017-07-16得票数 1
回答已采纳
1回答
我需要一种在有向图中找到第二最短路径的方法，在第二最短路径的顶部不能完全包含最短路径。我知道dijkstra algoritm算法，但我无法想出一个简单的方法来改变算法，让我在合理的时间内获得第二短路径。算法，子代码或c++示例，三者之一将非常感谢。
浏览 3提问于2016-06-12得票数 2
2回答
今天我遇到了这个词“单对最短路径问题”。我想知道对加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想，如果你想找到A和Z之间的最短路径，你绝对必须知道从A到B，C，D，……的最短路径。Y.如果你不知道后者，你就无法确定你的道路实际上是最短的。因此，对于我来说，任何最短路径算法都必须计算出图中从A到其他顶点的最短路径，才能
浏览 4提问于2017-03-30得票数 10
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
