回答情况：
提问时间：
问题标签：
我正试图使Python中的Bellman图形算法适应我的需要。下面是我在github：上找到的Bellman代码import math, urllib2, json, re
graph = {} jsrates = json.loads(page.read())
resul
浏览 3修改于2017-12-28得票数 4
回答已采纳
我在试着理解这个算法是如何工作的。我认为我必须按照以下步骤进行： topological sort of the graph put s in the queue while q is not empty我的问题是：
我的
浏览 0提问于2014-11-16得票数 1
在具有V节点和E边的有向图中，Bellman算法松弛每个顶点(或者更确切地说，每个顶点的边)(V-1)次。这是因为从源到任何其他节点的最短路径最多包含(V-1)边。在第V次迭代中，如果边可以放松，则表示存在负循环.实现这一目标的一种方法是运行Bellman，并注意负周期上的节点。然后，从这些节点运行DFS/BFS来标记其他节点。
然而，为什么我们不能在不诉诸DFS/BFS的情况下运行Bellman 2*(V-1)来检测这些节点呢？如果
浏览 0提问于2018-06-16得票数 0
回答已采纳
请推荐资源，了解如何使用Prim算法和Bellman-Ford算法在有向图中找到最小生成树，以计算有向图中的最短路径。
浏览 0修改于2012-01-30得票数 0
我尝试实现BF算法的负周期检测。def belman_ford(s, adj, cost): dist_arr = [MAX_VAL]*arr_len dist_arr[s] = 0
for i, v in enumerate(adj[u]):
浏览 0提问于2018-12-28得票数 1
回答已采纳
我目前的理解是，dijkstra的算法比贝尔曼-福特算法更有效，只是它不能处理负边缘。然而，假设我们有一个边权重图，其中有负权重的边，图中没有负权重的圈，我们还能使用dijkstra算法吗？
浏览 7提问于2019-11-28得票数 2
我正在Coursera上做“图上的算法”课程的练习，我必须实现Bellman-Ford算法来检测图是否有负圈，分别输出1和0。
浏览 0修改于2018-07-01得票数 2
假设我们想使用贝尔曼-福特最小化max_i x_i - min_i x_i受x_i - x_j <= c_{i，j}形式的m个约束我如何证明贝尔曼-福特算法可以在O(n*m)时间内解决这类问题？为每个变量x_i创建一个节点i创建从s到所有其他节点的0权重边
浏览 2修改于2013-04-11得票数 3
我使用队列实现了Bellman - Ford算法的解决方案，并将其性能与Dijkstra算法进行了比较。他们非常接近，这对我来说是一个惊喜，因为贝尔曼-福特的复杂性是O(NM)。我知道复杂性是最坏的情况，但结果仍然是令人惊讶的。我搜索了一些关于贝尔曼-福特的信息，我只在Sedgewick中找到了这句话，算法在Java中“在真实的网络上，贝尔曼-福特算法通常在线性时间内运行”。你能给我解释一下贝尔曼-福特算法的性能行为吗？
浏览 1提问于2009-06-15得票数 4
回答已采纳
我有一个贝尔曼-福特算法的实现。输入程序提供了一个边缘列表。在没有优化的情况下，它看起来像这样： for (i = 0; i < number_of_vertices; i++) { } for (i = 1; i < number_of_vertices - 1; ++i) {
for (j = 0; j < e; ++j) { //here i am ca
浏览 3提问于2016-05-12得票数 1
我正在做一个作业题，我需要从顶点z开始运行bellman-ford算法，它要求我“在每一次遍历中，以与图中相同的顺序放松边，并在每次遍历后显示d和pi值。”
浏览 0修改于2011-11-27得票数 2
回答已采纳
Dijkstra不能用于最长路径，因为它使用了当前最短路径肯定比其他路径短的属性。当然，假设没有负边权重，这是正确的。这也是为什么最长路径在Dijkstra上不起作用的原因，因为当前的最长路径不能保证以后不会有另一条更长的路径采用更大的值。 另一方面，贝尔曼福特提供了负重的灵活性，但性能较差。这意味着对于贝尔曼·福特来说，它不会像Dijkstra那样贪婪。这就是为什么我感到困惑的原因--为什么Bellman Ford不能用于单源最长路径问题(NP hard)？例如，我们可以简单地将图的所有权重乘以-1，并找到最短路径，这将是原始图的最长路径。
浏览 34提问于2020-08-25得票数 2
回答已采纳
我一直在尝试编写用于在图中寻找最短路径的Bellman Ford algoritm，虽然我已经有了一个有效的解决方案，但它运行得并不是很快，我相信如果我使用numpy而不是我目前的方法，它会更快。import os
vertices, edges = map(lambda x: int(x), file.readline().replace("\n
浏览 3修改于2013-01-17得票数 2
回答已采纳
我目前正在通过否定所有边权重并运行Bellman-Ford算法来寻找有向无环正权图中的最长路径。这工作得很好。
但是，我想打印使用了哪些节点/边的跟踪信息。我该怎么做呢？
浏览 3修改于2015-01-12得票数 1
回答已采纳
贝尔曼-福特算法如下所示for i = 1 to |G.V| - 1 call Relax(u,v,w)
这个伪代码索引从1开始，而不是0。 for i in range((len(self.V.keys()))-1): for edge in self.V[vertex]:
Q1:我们应
浏览 3修改于2011-12-02得票数 2
回答已采纳
我知道贝尔曼-福特算法适用于有向图。它是否适用于无向图？似乎对于无向图，它将无法检测循环，因为并行边将被视为循环。这是不是真的？该算法可以应用吗？
浏览 1修改于2018-04-25得票数 21
回答已采纳
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号