最短路dijkstra算法

小鱼儿 2022-12-20 08:39 107阅读 0赞

一直想着把这个板子存一下，但老是忘了，结果每次还得自己手打

dijkstra最短路算法有两种方法 第一种n^2的时间，用一个数组维护起点到所有点最短距离，不断的用最新点连进来的边来更新数组

第二种方法是 nlogm的 用一个优先队列来找出局部最优解，进而扩散至全局最优

？？？这么快就这么多人看

那我加点解释：

首先考虑n^2的解法是用一个除了起点，其余点距离初始值均为inf 的数组用于存放答案，然后把起点所连的边连过去用于更新答案数组，然后把起点标记，表示该点已经确定出答案了，然后从答案数组中找到除了标记点外的最近的点，重复加边更新答案数组的操作，再把该点标记，直至答案数组全被标记

局部最优解扩散至全局

而nlogm的算法是从n^2改进的，我们观察发现，我们可以吧每一次更新的可能都存到一个优先队列中，然后选出当前最优的来更新，然后把新最优点新增的边放进优先队列中即可。重复n次即可。（md讲的好差啊！建议b站找视频看，配合动态图学习该算法更佳，不过我好歹给了个模板题你们练 哈！）

[洛谷单源最短路板子题][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+7;
    typedef long long ll;
    const ll inf=1e18;
    int n,m,s,t;
    struct node
    {
        int to;
        ll w;
        bool operator<(const node &s) const
        {
    
            return w>s.w;
        }
    };
    vector<node>son[N];
    ll ans[N];
    void dijkstra()
    {
        priority_queue<node>p;
        for(int i=1;i<=n;i++) ans[i]=inf;
        p.push({s,0});
        while(p.size())
        {
            node a=p.top();
            p.pop();
            if(a.w>=ans[a.to]) continue;
            ans[a.to]=a.w;
            
            for(int i=0;i<son[a.to].size();i++)
            {
                node d=son[a.to][i];
                if(ans[d.to]>d.w+a.w)
                p.push({d.to,d.w+a.w});
            }
        }
    }
    int main()
    {
        //ios::sync_with_stdio(false);
       scanf("%d%d%d",&n,&m,&s);
       for(int i=1;i<=m;i++)
       {
           int a1,a2;ll a3;
           scanf("%d%d%lld",&a1,&a2,&a3);
           son[a1].push_back({a2,a3});
           //son[a2].push_back({a1,a3});
       }
       dijkstra();
       for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
      // printf("%lld\n",ans[n]);
    }

那再更点？

n^2 dijkstra(为了防止完全图的情况)

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+7;
    const ll inf=1e18;
    ll dis[N];
    int n,m,s,t;
    vector<pair<int,int>>son[N];
    int vis[N];
    void dijkstra()
    {
        for(int i=0;i<=n;i++) dis[i]=inf;
        dis[s]=0;vis[s]=1;
        int x=s;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<son[x].size();j++)
            {
                auto d=son[x][j];
                if(vis[d.first]) continue;
                dis[d.first]=min(dis[d.first],d.second+dis[x]);
            }
            x=0;
            for(int j=1;j<=n;j++)
            {
                if(vis[j]) continue;
                if(dis[j]<dis[x]) x=j;
            }
            vis[x]=1;
        }
    }
    int main()
    {
       cin>>n>>m>>s;
       for(int i=1;i<=m;i++)
       {
           int a1,a2,a3;
           cin>>a1>>a2>>a3;
           son[a1].push_back({a2,a3});
           son[a2].push_back({a1,a3});
       }
       dijkstra();
       for(int i=1;i<=n;i++) cout<<dis[i]<<' ';cout<<endl;
    }

再来一个 floyd的 二维数组存边权，为解决n小的情况 可以生成一个二维数组存放任意一个（i，j）的最短距离（方法是dp 不断迭代）（似乎n次dijkstra也可啊！）

for(int i=1;i<=n;i++)  
for(int j=1;j<=n;j++)  
for(int k=1;k<=n;k++)  
dis\[i\]\[j\]=min(dis\[i\]\[k\]+dis\[k\]\[j\],dis\[i\]\[j\]);

一个三重循环就完事了，

bellman-ford 算法我不会，之前似乎是学过的但是dijkstra够用了就忘掉了

[Link 1]: https://www.luogu.com.cn/problem/P4779