基于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，我们是否可以对从节点到it的边缘进行加权，并使用该代码在无向加权图中计算从顶点到其他每个顶点的最短路径？

Answer 1

对于BFS的大多数实现来说，答案是否定的，因为队列最终会出现错误的顺序-- BFS只保证在未加权图中的最短路径，因为队列顺序保证了第一次看到节点时必须通过最短路径到达它。

对于问题中的具体实现，答案实际上是肯定的，因为这个实现实际上并不禁止访问一个节点(以及它的邻居添加到队列中)不止一次，除非比较找到的路径是否比以前找到的路径长。这意味着通过非最短路径向队列中添加节点不会导致不正确的结果，因为稍后将通过其最短路径添加同一个节点，并更新其距离(导致其邻居也得到更新，等等)。这仅仅意味着您的算法可以多次访问一些节点，这使得它效率低下；但是它实际上会找到最短的路径。

如果您通过使用优先级队列而不是队列来解决这个问题，那么您就有了迪克斯特拉算法。