我们可以使用BFS（以最优的方式）来找到带权有向无环图中从源节点到所有其他节点的最短路径吗？

Question

我知道可以使用拓扑排序在 O(V+E) 内完成。但我认为使用 BFS 也可以以相同的复杂度完成。

Answer 1

拓扑排序只不过是一次 DFS 运行而已。然后，当每个顶点完成时，您将其放在链表的前面。它的运行时间为O(V+E)。正如我之前所说，我认为这里更自然地问“我们可以使用 BFS 进行拓扑排序吗？”。这已经被问过并回答过。

如果你的意思只是BFS，那么我会说不。看看这个示例。拓扑排序是其所有顶点的线性排序，如果图 G 包含边 (u, v)，则 u 在排序中出现在 v 之前。您可以在该示例中看到从 c 到 d 有一条边，但 d 出现在 c 之前。我认为您可以更新 BFS 来查找拓扑排序，但它与运行 DFS 具有相同的复杂性。我建议你看看这篇文章Using BFS for topological sort

Answer 2

使用简单的 BFS 并不是最优的，因为如果节点（A）已经从 INT_MAX 更新到某个 x 并推送到队列中，并且我们找到了一种以小于 x 的值到达 A 的方法，那么我们更新它现在再次推入队列，如果A已经在队列中，我们可以稍微降低时间复杂度，我们不推它，但是如果A不在队列中但已经处理过一次，那么我们必须再次推A等等相邻节点必须再次处理。

为了避免这种重复，我们按照拓扑排序的顺序旅行，这样我们就可以避免 这种循环。

Answer 3

不使用拓扑排序（使用堆栈的 dfs 方法），可以使用 bfs 来查找最短路径。但它不如使用拓扑排序有效。如果你想要它的代码。

    vector <pair <int,int>> adj[N];
     for(int i=0;i<M;i++){
         int first=edges[i][0];
         int second=edges[i][1];
         int dist=edges[i][2];
         
         adj[first].push_back({second,dist});
  
     }
     vector <int> dis(N,1e9);
    
     dis[0]=0;
     queue <int> s;
     s.push(0);
     while(!s.empty()){
         auto front=s.front();
         
         s.pop();
         
         for(auto it:adj[front]){
            
             if(dis[front]+it.second < dis[it.first]){
                 dis[it.first] = dis[front]+it.second;
                 
                  
                     s.push(it.first);
                  
             }
         }
     }
     for(int i=0;i<N;i++){
         if(dis[i]==1e9){
             dis[i]=-1;
         }
     }
     return dis;