Bellman-Ford算法

1 回答

• 0

  不，Bellman-Ford的最坏情况运行时间是O（E * V），因为必须在V-1次上迭代图形 . 但是，通过使用基于队列的Bellman-ford变体，我们实际上可以将Bellman-Ford改进到O（E V）的运行时间 .

  这是基于队列的Bellman-Ford实施 . 代码灵感来自书籍网站Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne

  private void findShortestPath(int src) {
      queue.add(src);
      distTo[src] = 0;
      edgeTo[src] = -1;
      while (!queue.isEmpty()) {
          int v = queue.poll();
          onQueue[v] = false;
          for (Edge e : adj(v)){
              int w = e.dest;
              if (distTo[w] > distTo[v] + e.weight) {
                  distTo[w] = distTo[v] + e.weight;
                  edgeTo[w] = v;
              }
              if (!onQueue[w]) {
                  onQueue[w] = true;
                  queue.add(w);
              }
  
              //Find if a negative cycle exists after every V passes
              if (cost++ % V == 0) {
                  if (findNegativeCycle())
                      return;
              }
          }
      }
  }
  

  该算法的最坏情况运行时间仍为O（E * V），但在该算法中通常实际上以O（E V）运行 .

  回复于 2024-05-04T20:02:18+08:00