Dijkstra算法是否最有效地计算单源最短路径？

Question

迪杰斯特拉算法是寻找单源最短路径的最有效方法吗？我正在使用此算法计算从站1（起始节点）到站N（目标节点）公交路线的最低车费。连接中间车站的路径有一个乘车费用（边权）。请注意，公交路线网络可能具有以下规模：

- 1 <= 车站数 <= 50000 - 1 <= 路径数 <= 500000

问题的详细信息可以在这里找到 - https://www.hackerrank.com/challenges/jack-goes-to-rapture 现在，我的代码逻辑是正确的，只有16个测试用例中的2个失败了。失败的原因是测试用例中的图形大小很大，执行时间导致超时。

我需要一些帮助来优化代码（Dijkstra算法）。如果有其他更适合大型图形的算法，也想了解一下。谢谢。

- wildthing81

---

A*搜索可能更快？ - Alyssa Haroldsen

如果你有一个好的启发式函数，或许A*算法会更好。 - ymonad

请查找带有地标和三角不等式的A星算法，也被缩写为ALT路径规划。 - Pieter Geerkens

查找带有地标和三角不等式的A星算法，也被称为ALT路径规划。这将解释如何构建和使用合适（即可接受的）的启发式算法以满足性能要求。Dijkstra算法通常具有O（N ^ 2）的性能。 - Pieter Geerkens

Dijkstra算法的复杂度为O(E log V)，使用“标准”实现（带有优先队列）。您还可以查看https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm。 - kfx

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

- Shree Vignesh