algorithm - Dijkstra 算法对于计算单源最短路径是否最有效？

Question

寻找单源最短路径的 Dijkstra 算法是无向图最有效的算法吗？我正在使用此算法来计算从站 1(起始节点)到站 N(目的地节点)的公交路线的最低票价。连接中间站的路径分配了票价(边权重)。注意，公交路线网络可以有

• 1<=站点<=50000
• 1<=路线<=500000

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

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

我可以使用一些帮助来优化代码(Dijkstra 算法)。如果还有其他算法可以更有效地处理大尺寸图，我也想知道。谢谢。

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