data-structures - 对加权无向图使用基于 BFS 的单源最短路径

Question

这是我遵循的教程的链接:https://www.youtube.com/watch?v=hwCWi7-bRfI&t=1106s
这是代码:

void BFS(vector<int> adj[], int N, int src) 
{ 
    int dist[N];
    for(int i = 0;i<N;i++) dist[i] = INT_MAX; 
    queue<int>  q;
    
    dist[src] = 0;
    q.push(src); 

    while(q.empty()==false) 
    { 
        int node = q.front(); 
        q.pop();
         
        for(auto it:adj[node]){
            if(dist[node] + 1 < dist[it]){
                dist[it]=dist[node]+1;
                q.push(it);
            }
        } 
    } 
    for(int i = 0;i<N;i++) cout << dist[i] << " "; 
} 

在 for 循环中，我们正在检查 if(dist[node] + 1 < dist[it]) ，而不是 +1，我们可以从 做边的权重吗？节点至 它并使用此代码计算无向加权图中从一个顶点到每个其他顶点的最短路径？

Answer 1

对于 BFS 的大多数实现，答案是否定的，因为队列最终会处于错误的顺序 - BFS 仅保证未加权图中的最短路径，因为队列顺序保证您第一次看到节点时必然是通过最短路径它的路径。
对于您问题中的具体实现，答案实际上是肯定的，因为该实现实际上并没有禁止一个节点被多次访问(并将其邻居添加到队列中)，除非通过比较找到的路径是否长于一个以前发现的。这意味着通过非最短路径将节点添加到队列不会导致错误结果，因为稍后将通过其最短路径添加相同的节点，并且其距离将被更新(导致其邻居也被更新) ， 等等)。这只是意味着你的算法可以多次访问某些节点，使其效率低下；但它实际上会找到最短路径。
如果您使用 priority queue 解决此问题而不是队列，那么你有 Dijkstra's algorithm .