文章/答案/技术大牛

发布

社区首页 >问答首页 >我修改了BFS以在加权无向图中找到最短路径，而不是使用Dijkstra的algo，它起作用了。

问我修改了BFS以在加权无向图中找到最短路径，而不是使用Dijkstra的algo，它起作用了。
EN

Stack Overflow用户

提问于 2021-09-11 22:17:12

回答 1查看 792关注 0票数 0

为了在无向加权图中找到最短路径，我比较了BFS和dijkstra的algo，以了解为什么我们需要优先级队列。

我编写了一些修改BFS的代码，以找到给定图中所有节点的最短路径。

问题链接:- https://practice.geeksforgeeks.org/problems/implementing-dijkstra-set-1-adjacency-matrix/1#

下面的代码在我写的GeeksForGeeks上被接受了，而不是dijkstra :-

 vector <int> dijkstra(int vertices, vector<vector<int>> graph[], int src)
  {
   // modified bfs

  vector<int> dist(vertices + 1,INT_MAX);
    queue<int> nodes;
    nodes.push(src);
    dist[src] = 0;
    while(!nodes.empty()){
        int curNode = nodes.front();
        nodes.pop();
        for(auto adjNode : graph[curNode]){
            if(dist[adjNode[0]] > dist[curNode] + adjNode[1] ){
                dist[adjNode[0]] = dist[curNode] + adjNode[1];
                nodes.push(adjNode[0]);
            }
        }
    }
    return dist;
}

问题：-虽然GeeksForGeeks接受了它，但我想知道它是不是错了，因为GeeksForGeeks可能有有限数量的测试用例？

问题：-或者如果这是一个正确的方法，那么时间的复杂性是什么？(也许是因为时间比dijkstra更复杂，所以没有使用上述方法)

c++

data-structures

graph

breadth-first-search

dijkstra

回答 1

Stack Overflow用户

回答已采纳

发布于 2021-09-12 00:10:12

您编写的算法是Bellman算法的一个变体。

算法是对Bellman算法(以及您的)的改进。SPFA和您的算法之间唯一的区别是，SPFA在推送顶点之前检查顶点是否已经在队列中。但其最坏的时间复杂度仍然是O(V^2)。

考虑到这个简单的情况，每次访问一个新的顶点时，您都会更新从这个顶点到vertex#2的长链。

       30
    ┌───────2
    │       │ 1
    │  20   │
    ├───────3
    │       │ 1
    │  15   │
1───┼───────4
    │       │ 1
    │  12   │
    ├───────5
    │       │ 1
    │  10   │
    └───────6

SPFA还有许多其他的优化变体，但大多数都比Dijkstra算法的时间复杂度更糟糕。一个简单的随机加权网格形状图可以使它们运行速度比Dijkstra的算法慢得多。

更新

SPFA与Dijkstra算法在网格形状图(现场演示)上的简单比较

dijkstra  27ms spfa  216ms    (V=300*300 E~=3V on https://godbolt.org/z/b8qbWdbEP)
dijkstra  12ms spfa   87ms    (V=300*300 E~=3V on my computer)
dijkstra 152ms spfa 4819ms    (V=1000*1000 E~=3V on my computer)

Update2

修改发电机(现场演示)使用固定的小重量垂直边缘。SPFA变得慢得多，这更直观地估计了它的时间复杂性。

dijkstra  12ms spfa   393ms  (V=200*200 on https://godbolt.org/z/hKnMqPvMM)
dijkstra   7ms spfa   192ms  (V=200*200 on my computer)
dijkstra  15ms spfa   653ms  (V=300*300 on my computer)
dijkstra 187ms spfa 40351ms  (V=1000*1000 on my computer)

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/69147098

复制

相似问题

问我修改了BFS以在加权无向图中找到最短路径，而不是使用Dijkstra的algo，它起作用了。
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问我修改了BFS以在加权无向图中找到最短路径，而不是使用Dijkstra的algo，它起作用了。EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问我修改了BFS以在加权无向图中找到最短路径，而不是使用Dijkstra的algo，它起作用了。
EN