前言

Dijkstra算法,是正权图中求单源最短路径的经典算法,其朴素算法时间复杂度为O(n^2^),加入优先队列优化(堆优化)后时间复杂度可以达到O((m+n)logn)。
图中可以存在环,但是给出的边权不能有负值。 正权图最好用Dijkstra算法,相较于SPFA算法比较稳定。~~(以上来自于洛谷大佬的总结)~~

为了更好地理解Dijkstra算法(优化),需要知道链式前向星和优先队列, 如果不太清楚可以看看这两篇文章:

  • 链式前向星:点击这篇文章
  • 优先队列:点击这篇文章
    (感谢这两位博主,文章写得真的很好)

OK,如果你已经知道了链式前向星和优先队列,下面我们开始正式做题。

洛谷 P3371 【模板】单源最短路径(弱化版)

SPFA算法模板题,以下给出AC代码,具体思路详见注释。
(SPFA运行效率低于Dijkstra,若出题人构造出毒瘤数据可以让SPFA超时,这题是弱化版,所以能过)

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=5e5+10;
int n,m,x,y,z,s,cnt,dis[N],vis[N],head[N];
struct edge
{
    int w,to,next;
}e[M];//定义边的三个信息,w表示边权,to表示边的终点,next表示上一条边
void add(int x,int y,int z)//链式前向星存边
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];//next表示以x为起点的上一条边的编号
    head[x]=cnt++;//head[x]表示以x为起点的最后一条边的编号
}
queue<int>q;
void spfa()
{
    q.push(s);//起点入队
    dis[s]=0;//起点到自身距离为0
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;//出队标记
        for(int i=head[u];i!=-1;i=e[i].next)//遍历以u为起点的所有边
        {
            int v=e[i].to;
            if(dis[u]+e[i].w<dis[v])
            {
                dis[v]=dis[u]+e[i].w;//更新最短距离
                if(vis[v]==0)
                    q.push(v),vis[v]=1;//入队标记
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));//head数组初始化
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
    }
    for(int i=1;i<=n;i++)//dis数组初始化
        dis[i]=2147483647;
    spfa();
    for(int i=1;i<=n;i++)
        i==n?printf("%d\n",dis[i]):printf("%d ",dis[i]);
    return 0;
}

洛谷 P4779 单源最短路径(标准版)

Dijkstra算法模板题,以下给出AC代码,具体思路详见注释。
(本题用SPFA会超时,只能用Dijkstra)

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,m,x,y,z,s,cnt,dis[N],vis[N],head[N];
struct edge
{
    int w,to,next;
}e[M];//定义边的三个信息,w表示边权,to表示边的终点,next表示上一条边
void add(int x,int y,int z)//链式前向星存边
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];//next表示以x为起点的上一条边的编号
    head[x]=cnt++;//head[x]表示以x为起点的最后一条边的编号
}
struct node
{
    int u,w;//u为点的编号,w为到u点的最短路即dis[u]
};
bool operator < (const node &s1,const node &s2)//重载运算符,优先队列中的自定义排序
{return s1.w>s2.w;}//注意写大于号还是小于号与实际的符号相反,实际是小于号,则要写大于号
priority_queue<node>q;
void dijkstra()
{
    q.push({s,0});//起点入队
    dis[s]=0;//起点到自身距离为0
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;//保证每个点只被访问一次
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next)//遍历以u为起点的所有边
        {
            int v=e[i].to;
            if(dis[u]+e[i].w<dis[v])
            {
                dis[v]=dis[u]+e[i].w;//更新最短距离
                q.push({v,dis[v]});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));//head数组初始化
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
    }
    for(int i=1;i<=n;i++)//dis数组初始化
        dis[i]=2147483647;
    dijkstra();
    for(int i=1;i<=n;i++)
        i==n?printf("%d\n",dis[i]):printf("%d ",dis[i]);
    return 0;
}

讨论重载运算符的写法:https://www.luogu.org/blog/53164/dijkstra-heap

洛谷 P1144 最短路计数

SPFA代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=100003;
int n,m,x,y,cnt,dis[N],ans[N],vis[N],head[M];
struct edge
{
    int w,to,next;
}e[M<<1];//无向图,边数乘2
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
queue<int>q;
void spfa()
{
    q.push(1);dis[1]=0;ans[1]=1;//从1开始,到1自身的最短路径只有1条,最短路径长度为0
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;//出队标记
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            if(dis[to]>dis[x]+e[i].w)
            {
                ans[to]=ans[x];
                dis[to]=dis[x]+e[i].w;
                if(!vis[to])
                {
                    vis[to]=1;//入队标记
                    q.push(to);
                }
            }
            else if(dis[to]==dis[x]+e[i].w)
                ans[to]=(ans[to]+ans[x])%mod;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);//注意是无向图,输入的是一条边的信息,实际上要存储的是两条边的信息(还包括反向的)
    }
    spfa();
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

Dijkstra代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=100003;
int n,m,x,y,cnt,dis[N],ans[N],vis[N],head[M];
struct edge
{
    int w,to,next;
}e[M<<1];//无向图,边数乘2
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
struct node
{
    int w,now;
    bool operator < (const node &x) const
    {return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
    q.push({0,1});dis[1]=0;ans[1]=1;//从1开始,到1自身的最短路径只有1条,最短路径长度为0
    while(!q.empty())
    {
        int x=q.top().now;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            if(dis[to]>dis[x]+e[i].w)
            {
                ans[to]=ans[x];
                dis[to]=dis[x]+e[i].w;
                q.push({dis[to],to});
            }
            else if(dis[to]==dis[x]+e[i].w)
                ans[to]=(ans[to]+ans[x])%mod;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);//注意是无向图,输入的是一条边的信息,实际上要存储的是两条边的信息(还包括反向的)
    }
    dijkstra();
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

洛谷 P2243 电路维修

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,t,c,cnt,x[N],y[N],z[N],dis[N],vis[N],head[N];
struct edge
{
    int w,to,next;
}e[N];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
struct node
{
    int w,now;
    bool operator < (const node &x) const
    {return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
    q.push({0,1});dis[1]=0;
    while(!q.empty())
    {
        int x=q.top().now;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            if(dis[x]+e[i].w<dis[to])
            {
                dis[to]=dis[x]+e[i].w;
                q.push({dis[to],to});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;char f;
    while(t--)
    {
        memset(head,-1,sizeof(head));
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));cnt=0;
        cin>>n>>m;c=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>f;
                if(f=='/')
                {
                    x[++c]=(i-1)*(m+1)+j+1,y[c]=x[c]+m,z[c]=0;
                    x[++c]=(i-1)*(m+1)+j,y[c]=x[c]+m+2,z[c]=1;
                }
                else
                {
                    x[++c]=(i-1)*(m+1)+j,y[c]=x[c]+m+2,z[c]=0;
                    x[++c]=(i-1)*(m+1)+j+1,y[c]=x[c]+m,z[c]=1;
                }
            }
        for(int i=1;i<=c;i++)
        {
            add(x[i],y[i],z[i]);
            add(y[i],x[i],z[i]);//注意是双向的无向图!!!
        }
        dijkstra();
        if(dis[(n+1)*(m+1)]==0x3f3f3f3f)printf("NO SOLUTION\n");
        else printf("%d\n",dis[(n+1)*(m+1)]);
    }
    return 0;
}

洛谷 P1186 玛丽卡

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e6+10;
int n,m,f,x,y,z,cnt,ans,dis[N],vis[N],head[M],flag[N][N],pre[N];
struct edge
{
    int w,to,next;
}e[M];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
struct node
{
    int w,now;
    bool operator < (const node &x) const
    {return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    q.push({0,1});dis[1]=0;
    while(!q.empty())
    {
        int x=q.top().now;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            if(flag[x][to]==0&&dis[to]>dis[x]+e[i].w)
            {
                if(f==0)pre[to]=x;
                dis[to]=dis[x]+e[i].w;
                q.push({dis[to],to});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    dijkstra();
    f=1;
    for(int i=n;i!=1;i=pre[i])
    {
        flag[pre[i]][i]=1;
        flag[i][pre[i]]=1;
        dijkstra();
        flag[pre[i]][i]=0;
        flag[i][pre[i]]=0;
        ans=max(ans,dis[n]);
    }
    printf("%d\n",ans);
    return 0;
}

参考文章,最短路最长路整理:https://blog.csdn.net/yusiningxin/article/details/50758946