2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。input A
set B[i, j] = 0 for i = 1 to n:
浏览 8提问于2021-02-22得票数 1
我正在使用networkx做一些工作，并使用了两种最短路径算法，即： dijkstra_path(G, source, target[, weight])
我知道dijkstra_path(G, source, target[, weight])函数基于dijkstra的最短路径算法。我想知道shortest_path(G[, source, target, weight])函数所基于的<
浏览 6提问于2014-07-28得票数 2
回答已采纳
1回答
根据问题的具体情况，在单源最短路径问题中通常提到的两种算法是Dijkstra算法和Bellman算法。Dijkstra的算法工作在正边权值，而Bellman算法是一个推广，也允许负边权。正如Sedgewick的“算法”(第4版)所实现的，Dijkstra的算法是基于优先级队列的</em
浏览 7提问于2015-04-18得票数 0
1回答
我想解决一个本地程序竞赛的问题。这个问题基本上是关于在加权图中寻找最短路径。我对这些类型的问题非常陌生，我想我可以使用Dijkstra的算法。然而，有一个小的复杂性-某些值是不同的，取决于当前路径的情况。有两种类型的权重:正常权重和有条件的权重(我们称之为K)。条件是:当你用权K穿过边时，所有其他类型的
浏览 5提问于2017-02-16得票数 2
回答已采纳
1回答
您可以对此图G进行任何预处理(对于具有几千个顶点的图，您可以在合理的时间和空间约束下进行预处理，因此不能只存储所有可能的答案)。
现在假设我选择了一个子集V'的V。我希望MST只在这些顶点V'上。
浏览 5提问于2017-08-29得票数 0
2回答
我正在尝试理解A*，统一成本和贪婪搜索算法是如何工作的。我知道探索节点的方式在所有三种算法中都会发生变化(贪婪将基于启发式值进行探索，A*基于启发式加距离，均匀基于距离)。我想知道，对于给定的源和目的地，是否所有3种算法都应该提供最短路径(只需探索不同数量的城市？)或者他们能提供一条不同的路径。我最困惑的是实现部分-如果你将节点存储在队列中，那么当你打算探索目标节点时，你将拥有它的
浏览 4提问于2016-10-04得票数 1
我读到了有关图算法的文章，我发现了这两种算法：
我找了很多关于这件事，但没有得到满意的答案！在图中查找最短路径的BFS规则如下：
存储从源u到顶点v的距离(重量/长度)。更新的路径从源u到那个顶点v<em
浏览 8提问于2014-08-22得票数 65
回答已采纳
我有一个家庭作业，我要找出两个城市之间最便宜的机票，考虑到中途停留。DijkstraAlgorithm(weighted simple digraph, vertex first)
我很难理解的是--尤其是在看整个伪代码的时候--为什么它只接受一个顶点作为参数我需要找到两个顶点之间最便
浏览 4提问于2011-12-05得票数 2
回答已采纳
2回答
给出了一个无向图，它具有普通边和特殊边，我们的目的是求出两个顶点(从顶点到顶点)之间的最短路径权值的和，其只遍历等于或少于一次<code>E 210</code>。换句话说，有多个特定的边，最多只能使用其中一个。
这是我在数据结构家庭作业中遇到的一个问题，我坚持了在图中存储边的权重的第一步。因为图中有两种边，所以我不知道如何解决这个问题。我知道使用Dijkstra
浏览 1提问于2021-12-06得票数 1
回答已采纳
1回答
作为一项任务，我得到了以下问题，但这确实使我感到困惑：
考虑BFS算法。给定有向图G = (V，E)和起始点s∈V，该算法计算每个顶点u∈V的值du，即从s到u最短路径上的长度(边数)，该问题的目的是修改类的BFS算法，计算从s到G的每个顶点的最短路径数。解释如何使用该BFS的结果生成一个新的有向图G2 =(V2，E2)，其中
浏览 2提问于2015-04-26得票数 3
我知道，如果算法达到负循环，算法就不会终止，如果路径包含一个距离大于0的循环，那么它就不是最短路径。
我的问题是，如果存在一个循环距离为0的最短路径会发生什么，算法会将该循环包含在最短路径中吗？你会说所有的最短路径都是非循环的吗？
浏览 13提问于2017-06-20得票数 0
现在有一个很大的无向图网络，我想计算出无向图的所有顶点之间的最短路径，但是效率很低，我可以分割和合并这个无向图吗？目前使用的Java库是jgrapht。目前，顶点的数目是8000+，内存消耗和计算时间消耗都很严重。
浏览 1提问于2021-09-17得票数 1
1回答
Bellman算法是求解单源最短路径问题的有效算法，它在kth迭代中对每个顶点都有一个独特而有趣的k-跳最优性，这是我的应用程序所必需的。(基本上，我希望在一对顶点之间有一条最多k跳的最短路径)
由于J. Yen的原因，Bellman有两种，这可以将复杂度从O( the ^3)降低到O(the_x^3/4)。也就是说，在计算中以等于1/4的常数
浏览 2提问于2014-09-08得票数 0
回答已采纳
3回答
我很难理解的用处。我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢，但我想不出来。根据维基百科，Johnson算法使用Bellman Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法查找最短路径。但贝尔曼·福特算法也是一种寻找最短路径的算法。为什么我们不使用从贝尔曼·福特算法得到的最短路径呢？
浏览 0提问于2011-03-16得票数 4
回答已采纳
因此，dijkstra算法是搜索加权(无负)连通图最短路径的最佳算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。
问题:我的理解正确吗？它也能用来寻找某些顶点的最短路径吗？例如，图有A，B，C，D，E，F，G，H，I，J，K，我们只对A，B；C，K的最短路感兴趣，我们可能只需
浏览 2提问于2018-03-12得票数 1
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
我最近正在学习图形算法，在我的大学里，我们被教导说，Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对最短路径)。然而，我不明白这个算法是如何实现的，我试图通过观看YouTube视频和查找维基百科中的定义来理解它……我无法找到描述该算法的资源，其结果将是所有对最短路径表，但只能“从一个节点到所有其他节点对Bellman算法进行调整
浏览 8提问于2017-07-16得票数 1
回答已采纳
我目前正在研究Bellman算法，出现了一个疑问。据我所知，Bellman算法从它的来源创建最短路径，如果图中有一个负循环，它返回true，算法停止，另一方面，它用最短路径返回false。我现在的问题是，该算法是避免了图中创建最短路径的正循环，还是没有考虑到它们(因而落入了它们的陷阱)？
提前感谢！
浏览 4提问于2022-01-12得票数 1
回答已采纳
我目前正在研究非负边权图中的最短路径问题。我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路</em
浏览 4提问于2022-05-11得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
