Dijkstra的算法对于计算单源最短路径最有效吗？

Question

对于无向图，Dijkstra的单源最短路径算法是最有效的算法吗？我使用这个算法来计算从站1(开始节点)到站N(目的地节点)的公交线路的最低票价。连接中间站的路径有一个指定的车费(边缘权重).Note，该公交线路网络可以有

• 1<=Stations<=50000
• 1<=Routes<=500000

这个问题的细节可以在这里找到- https://www.hackerrank.com/challenges/jack-goes-to-rapture

现在，我的代码的逻辑是合理的，因为在16个测试用例中，只有2个有failed.The失败的原因是测试用例中的图形大小很大，执行时间导致超时。

我需要一些帮助来优化代码(Dijkstra的算法)。如果有其他算法可以更有效地处理大尺寸的图形，那么想知道它是well.Thanks。

Answer 1

您可以从队列到优先级队列来优化它。

检查下面的代码

#include<bits/stdc++.h>
#define mod 1000000000000
using namespace std;

typedef long long int ll;
typedef long double ld;

vector<ll> pred1,pred2;
vector<ll> dist1,dist2;
vector<ll> vis1,vis2;
vector< pair<ll,ll> > v[100005];

class compare{

public:
    bool operator()(pair<ll,ll> x,pair<ll,ll> y)
    {
        return x.second>y.second;
    }
};

bool cmp(ll x,ll y)
{
    return x>y;
}

int main()
{
    ll n,k,x,y,d;
    cin>>n>>k;
    pred1.clear();
    dist1.clear();
    vis1.clear();
    dist1.resize(n+5);
    vis1.resize(n+5);
    pred1.resize(n+5);
    for(ll i=0;i<=n;i++)
    {
        dist1[i]=mod;
        pred1[i]=0;
        v[i].clear();
    }
    for(ll i=0;i<k;i++)
    {
        cin>>x>>y>>d;
        v[x].push_back(make_pair(y,d));
        v[y].push_back(make_pair(x,d));
    }
    ll a,b;
    a=1;
    b=n;
    dist1[a]=0;
    priority_queue< pair<ll,ll> , vector< pair<ll,ll> > , compare > q;
    pair<ll,ll> p={a,0};
    q.push(p);
    while(q.size()!=0)
    {
        p=q.top();
        q.pop();
        if(vis1[p.first]==true)
            continue;
        vis1[p.first]=true;
        ll idx=p.first;
        for(ll i=0;i<v[idx].size();i++)
        {
            if(dist1[v[idx][i].first]>dist1[idx]+( (v[idx][i].second-dist1[idx]>=0) ? (v[idx][i].second-dist1[idx]) : 0 ) )
            {
                dist1[v[idx][i].first]=dist1[idx]+( (v[idx][i].second-dist1[idx]>=0) ? (v[idx][i].second-dist1[idx]) : 0 );
                q.push(make_pair(v[idx][i].first,dist1[v[idx][i].first]));
                pred1[v[idx][i].first]=idx;
            }
        }
    }
    if(dist1[b]==mod)
    {
        cout<<"NO PATH EXISTS\n";
        return 0;
    }
    cout<<dist1[b]<<"\n";

return 0;
}