这种基于 BFS 的算法是否适用于在加权图中找到最短路径

Question

我知道普通BFS搜索可以用于在未加权图或具有相同边权的图中寻找最短路径，而Dijkstra应该在加权图中使用，Dijkstra可以看作是BFS的变体。

但我想知道是否每次更新 dist[w] 时都将节点推送到队列中，而不是在普通 BFS 搜索中只推送一次，这个算法是否适用于寻找最短路径？我在一个 leetcode 问题上尝试了这个算法，它成功了，但是 leetcode 问题只检查有限的测试用例，所以我无法证明这个算法的正确性。如果算法正确，时间复杂度是多少？

   vector<int>dist(N + 1, INT_MAX);
        dist[start] = 0;
        queue<int>q;
        q.push(start);
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(auto [w, cost] : g[v]){
              //  cout<<w<<" "<<cost<<endl;
                if(cost + dist[v] < dist[w]){
                    dist[w] = cost + dist[v];
                    q.push(w);
                }
            }
        }

Answer 1

我相信您已经重新发现了 Bellman-Ford 算法，减去了负权重循环失败的必要处理。它应该运行在 O(|V| * |E|) 时间内（与 Dijkstra 的 O((|V| + |E|) * lg(|V|)) 相对）假设没有负循环，这将无限循环您的实现。好的部分是它处理负边权重，而 Dijkstra 没有。不好的部分是它慢得多。

见https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

这种基于 BFS 的算法是否适用于在加权图中找到最短路径

Does this BFS-based algorithm work for find shortest path in weighted graph

algorithm

breadth-first-search

shortest-path