Dijkstra最短路径算法实现错误（使用C++ STL）

Question

我尝试使用 std::priority_queue 在 C++ 中实现 Dijkstra 算法。函数“dijsktra”将输入 2 个节点，即源顶点和目标顶点。但是，我每次都得到不正确的答案。请帮帮我，告诉我哪里做错了。我的代码-

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#define inf 9999999
using namespace std;

map <int,int> vis;
vector <vector <pair <int,int> > > adj(100);
vector <int> dist(100);

void dijkstra(int u,int t)
{
    priority_queue <pair <int,int> > q;
    int b,w,i;
    q.push({0,u});
    vis[u]=1;
    
    while(!q.empty())
    {
        u = q.top().second; q.pop();
        
        if(!vis[u])
        {
            vis[u]=1;
            for(i=0;i<adj[u].size();i++)
            {
                b = adj[u][i].first; w = adj[u][i].second;
                if(dist[b]>dist[u]+w)
                {
                    dist[b] = dist[u] + w;
                    q.push({-dist[b],b});
                }
            }
        }
    }
    
    cout << dist[t];
}


int main()
{
    int i,j,k,n,m,x,y,w,t;
    
    cin >> n >> m;
    for(i=0;i<m;i++)
    {
        cin >> x >> y >> w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    
    cin >> t;
    
    for(i=1;i<=n;i++)
    {
        dist[i]=inf;
    }
    
    dijkstra(1,t);
}

Answer 1

问题是 vis[u]=1; 就在 q.push({0,u}); 之后。

因此，无法通过检查if(!vis[u])，不会处理任何节点。

你应该 dist[u]=0; 而不是那个。

Answer 2

错误：

由于 vis[u] = 1 永远不会让您进入 for 循环，因此您的代码无法运行。

实际上 Dijkstra algorithm 中不需要 visited array（至少对于这种情况）。但是这里用visited array会降低时间复杂度，有负边的时候会很棘手，所以要小心。

#include <iostream>
#include <vector>
#include <queue>
#define inf 9999999

std::vector <std::vector <std::pair <int,int> > > adj(100);
std::vector <int> dist(100);

void dijkstra(int u,int t)
{
    std::priority_queue <std::pair<int, int>> q;
    int b, w, i;

    q.push({0, u});
    while(!q.empty()) {
        u = q.top().second; 
        q.pop();
        for(i = 0; i < adj[u].size(); i++) {
            b = adj[u][i].first; w = adj[u][i].second;
            if(dist[b] > dist[u] + w) {
                dist[b] = dist[u] + w;
                q.push({-dist[b], b});
            }
        }
    }
    
    std::cout << dist[t];
}


int main()
{
    int i, n, m, x, y, w, t;
    
    std::cin >> n >> m;
    for(i = 0;i < m; i++) {
        std::cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    
    std::cin >> t;
    
    for(i = 0; i < n; i++) {
        dist[i] = inf;
    }
     
    // making the source distance to 0
    dist[0] = 0;
    
    dijkstra(0,t);
}

Dijkstra最短路径算法实现错误（使用C++ STL）

Error in Dijkstra's shortest path algorithm implementation (using C++ STL)

c++

algorithm

stl

dijkstra

graph-algorithm