我修改了 BFS 以在加权无向图中找到最短路径而不是使用 Dijkstra 的算法并且它有效

Question

为了在无向加权图中找到最短路径，我比较了 BFS 和 dijkstra 的算法理解为什么我们需要优先队列。
我写了一些修改 BFS 的代码来找到给定图中所有节点的最短路径。
问题 link :- 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 算法，所以未使用上述方法）

Answer 1

你写的算法是Bellman-Ford Algorithm的变体。

Shortest_Path_Faster_Algorithm 是 Bellman–Ford 算法（以及您的算法）的改进。 SPFA 和您的算法之间的唯一区别是 SPFA 在推送顶点之前检查顶点是否已经在队列中。但是它最坏情况的时间复杂度还是O(V^2).

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

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

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

更新:

SPFA和Dijkstra算法在网格形状图上的简单比较(live demo):

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)

更新2:

修改了生成器（live demo）以对垂直方向使用固定的小权重边缘。 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)

我修改了 BFS 以在加权无向图中找到最短路径而不是使用 Dijkstra 的算法并且它有效

I modified BFS to find shortest path in weighted undirected graph instead using Dijkstra's algo and it worked

c++

data-structures

graph

breadth-first-search

dijkstra