标签: bellman-ford

我正在为过去的课程之一设置问题。我应该实现Bellman Ford Algorithm，这样从源头上s我必须找到以下内容：

1. 如果从s（输出为*）无法访问该节点
2. 如果该节点可访问但属于负周期，因此没有最短路径（输出为-）
3. 否则，输出s到节点的最短路径

我编写了以下代码，该代码在未知的测试案例中失败。有人可以帮我调试吗？

void relax_edges(vector <vector<int>> &adj, 
                 vector <vector<int>> &cost, 
                 vector<long long> &dis) 
  {
  /*Takes input as adjacency list and relax all possible edges
  */

  for (int i = 0; i < adj.size(); i++) {
    for (int j = 0; j < adj[i].size(); j++) {
      if (dis[i] < std::numeric_limits < long long > ::max() 
             && dis[adj[i][j]] > dis[i] + cost[i][j]){
        //std::cout<< adj[i][j]<<" "<<i<<"\n";
        dis[adj[i][j]] = dis[i] …

我正在用 Python 实现 GeeksForGeeks 中的贝尔曼·福特算法。我想使用一些库（如 pyplot 或 networkx 或类似的库）生成图表（图表形式，而不是字典类型 - 这很容易）。我希望图形 UI 包含节点、边和相应的成本。

from collections import defaultdict 

#Class to represent a graph 
class Graph: 

    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = [] # default dictionary to store graph 

    # function to add an edge to graph 
    def addEdge(self,u,v,w): 
        self.graph.append([u, v, w]) 

    # utility function used to print the solution 
    def printArr(self, dist): 
        print("Vertex   Distance from Source") 
        for i in range(self.V): 
            print("%d \t\t %d" % (i, dist[i])) 

    # The …

我一直在搜索贝尔曼-福特算法的空间复杂度，但在维基百科贝尔曼-福特算法上，它说空间复杂度是 O(V)。在这个链接上它说 O(V^2) 。我的问题是；什么是真正的空间复杂度，为什么？

我最近正在学习图算法，在我的大学里我们被教导，贝尔曼-福特的结果是一个从所有节点到所有其他节点的距离表（所有对最短路径）。然而我不明白这个算法是如何实现的，并试图通过观看 YouTube 视频和在维基百科等中查找定义来理解它......

现在问题来了：
我找不到以某种方式描述算法的资源，结果将是所有对最短路径表，但只能是“从一个节点到所有其他节点”。

是否可以调整贝尔曼-福特算法以实现所有对最短路径表，或者我的大学讲师对此完全错误吗？（他确实解释了一些提供所有对最短路径的算法，他称之为贝尔曼福特，但我认为这不可能是贝尔曼福特）

编辑：我完全理解“从一个节点到所有其他节点的最短路径”问题的贝尔曼-福特算法。
我也了解我大学教授的“所有对最短路径”的大部分算法。
我只是很困惑，因为我大学的算法也被称为“贝尔曼-福特”。
如果您说德语：这是一个视频，其中大学讲师谈论他的“贝尔曼-福特”（我认为实际上不是贝尔曼-福特）：
https://www.youtube.com/watch ?v=3_zqU5GWo4w&t=715s