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

提问者：小点点

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

我曾尝试用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);
}

共2个答案

匿名用户

错误:

由于vis[u]=1从不允许您进入for循环，您的代码无法工作。

实际上，在Dijkstra算法中不需要有一个访问数组（至少在本例中是这样）。但是在这里使用访问数组将降低时间复杂度，并且当存在负边时，这将很棘手，所以在这里要小心。

#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);
}

匿名用户

问题是vis[u]=1；正好在q.push（{0，u}）；之后。

因此，无法传递检查if（！vis[u])，并且不会处理任何节点。

您应该执行dist[u]=0；而不是该操作。

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

共2个答案

相关问题