以下说明中用n表示结点数量，m表示边的数量
一般稠密图用邻接表存储，稀疏图用邻接矩阵存储

朴素dijkstra

• 适用范围:稠密图（m$\approx$n$^2$)
• 时间复杂度：O(n$^2$)

#include<iostream>
#include<cstring>
using namespace std;

const int N=510,M=1e5+10;
int n,m,map[N][N],dist[N];
bool st[N];     // 记录结点的距离是否确定

int dijktra()
{
    dist[1]=0;  // 令结点1的距离为0
    for(int i=1;i<=n;i++)   // n次循环，每次确定一个点的距离
    {
        int t=-1;
        for(int j=1;j<=n;j++)   //找到未确定距离点中距离最小的点 总共执行n^2次
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
            t=j;
        }

        if(t==n) break;
        st[t]=true;     // 找到当前未确定点集中离原点最近的点

        for(int j=1;j<=n;j++)   // 用确定的点t更新其他点
        {
            //自环不影响，假设存在自环 dist[j]<dist[j]+map[j][j]
            //邻接矩阵本身就可以看作每个结点都存在距离为无穷的自环
            dist[j]=min(dist[j],dist[t]+map[t][j]);  
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(map,0x3f,sizeof map);    //邻接矩阵初始化为最大值
    memset(dist,0x3f,sizeof dist);  //每个点到原点初始化为最大值
    cin>>n>>m;
    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        map[a][b]=min(map[a][b],w); //保留最短的边
    }

    int ans=dijktra();
    cout<<ans;
}

堆优化dijkstra

• 适用范围:稀疏图（m$\approx$n)
• 时间复杂度：O(mlog(m))$\approx$O(nlog(n))<O(n$^2$) 当m$\approx$n$^2$时，朴素版更优

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=2e5;
int e[N],ne[N],w[N],idx=0,n,m,h[N],dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap; // 小根堆
    heap.push({0,1});   // 结点1的距离为0 入堆
    dist[1]=0;
    while(heap.size())
    {
        PII t=heap.top();   // 每次O(1) 最多m次 
        heap.pop();

        int ver=t.second,distance=t.first;
        if(st[ver]==true) continue;     //如果ver已经确定过了，直接跳过 因为有重边
        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i]) //遍历与ver相接的结点 最多插入m次，共计O(mlog(m))
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                // 把更新过的结点和距离入堆
                // 即使存在重边，较短的边也会排在前面
                dist[j]=distance+w[i];
                heap.push({dist[j],j}); 
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int ans=dijkstra();
    cout<<ans;

}

bellman_ford

• 适用范围:存在负权边，限制经过的边的条数
• 时间复杂度：O(nm)

#include<iostream>
#include<cstring>
using namespace std;

const int N=510,M=10010;
int n,m,k,dist[N],backup[N];
struct Edge
{
    int a,b,c;
}edge[M];

int bellman_ford()
{
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);    // 只用上一次的更新结果更新所有点，防止点串联更新
        for(int j=0;j<m;j++)
        {
            int a=edge[j].a,b=edge[j].b,c=edge[j].c;
            dist[b]=min(dist[b],backup[a]+c);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1; //负权边可能把不能到达的点的距离更新
    else return dist[n];
}

int main()
{
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i]={a,b,c};
    }
    int ans=bellman_ford();
    if(ans==-1) puts("impossible");
    else cout<<ans;
}

spfa

• 适用范围:存在负权边
• 时间复杂度：最坏O(nm)

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=1e5+10;
int e[N],ne[N],w[N],idx,h[N],n,m,dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int spfa()
{
    queue<int> q;
    q.push(1);
    dist[1]=0;

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j]) 
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int ans=spfa();
    if(ans==-1) puts("impossible");
    else cout<<ans;
}

spfa判断负环

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=2010,M=1e4;
int h[M],e[M],ne[M],w[M],idx=0,dist[N],cnt[N],n,m;
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

bool spfa()
{
    queue<int> q;
    for(int i=1;i<=n;i++) //负环不一定在1-n的结点上，所以将所有结点都加入队列
    {
        q.push(i);
        st[i]=true;
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                // 某个结点出现大于n条边，说明存在环形回路，能迭代的前提是路径能更新，所以一定是负权回路
                if(cnt[j]>=n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }

            }
        }
    }
    return false;
}

int main()
{
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    if(spfa()) puts("Yes");
    else puts("No");
}