单源最短路

朴素Dijkstra

时间复杂度：O($n^2$)
适用：稠密图、边权为正数

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

const int N = 510, M = 1e5 + 10;
int f[N][N], d[N], n, m;
bool st[N];

int Dijkstra()
{
    d[1] = 0;
    for(int i = 0 ; i < n ; i ++ )
    {
        int t = -1;
        for(int j = 1 ; j <= n ; j ++ )
            if(!st[j] && (d[j] < d[t] || t == -1))
                t = j;
        st[t] = true;
        for(int j = 1 ; j <= n ; j ++ )
            d[j] = min(d[j], d[t] + f[t][j]);
    }
    if(d[n] == 0x3f3f3f3f)return -1;
    return d[n];
}
int main()
{
    memset(d, 0x3f, sizeof d);
    memset(f, 0x3f, sizeof f);
    cin >> n >> m;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b] = min(f[a][b], c);
    }
    cout << Dijkstra() << endl;
    return 0;
}

堆优化版Dijkstra

时间复杂度：O(mlogn)
适用：稀疏图、边权都是正数

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

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

void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int Dijkstra()
{
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int vex = t.second, dis = t.first;
        if(st[vex])continue;
        st[vex] = true;
        for(int i = h[vex] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(d[j] > dis + w[i])
            {
                d[j] = dis + w[i];
                heap.push({d[j], j});
            }
        }
    }
    if(d[n] == 0x3f3f3f3f)return -1;
    return d[n];
}
int main()
{
    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << Dijkstra() << endl;
    return 0;
}

Bellman-Ford

时间复杂度:O(nm)
适用:可用于存在负权边的图、根据抽屉原理可判断是否存在负环、经过k条边能否到达

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

const int N = 510, M = 10010;
struct Edge{
    int from, to, w;
}edge[M];
int n, m, k, d[N], bd[N];

void bellman()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 0 ; i < k ; i ++ )
    {
        memcpy(bd, d, sizeof d);
        for(int j = 0 ; j < m ; j ++ )
        {
            int from = edge[j].from, to = edge[j].to, w = edge[j].w;
            d[to] = min(d[to], bd[from] + w);
        }
    }
    if(d[n] > 0x3f3f3f3f / 2)cout << "impossible" << endl;
    else cout << d[n] << endl;
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0 ; i < m ; i ++ )
        cin >> edge[i].from >> edge[i].to >> edge[i].w;
    bellman();
    return 0;
}

spfa

时间复杂度:一般O(m),最坏(nm)
适用:边权可以为负数，可以判断是否存在负环，一般情况比Dijkstra还好

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

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

void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int spfa()
{
    d[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];//更新最短距离
                if(!st[j])//如果在队列中就不需重复添加
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    if(d[n] > 0x3f3f3f3f / 2)cout << "impossible" << endl;
    else cout << d[n] << endl;
}
int main()
{
    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();
    return 0;
}

多源最短路

Floyd

时间复杂度:O($n^3$)
适用:可存在权值为负数的边

#include<iostream>
using namespace std;

const int N = 210;
int n, m, k, f[N][N];

void floyd()
{
    for(int k = 1 ; k <= n ; k ++ )
        for(int i = 1 ; i <= n ; i ++ )
            for(int j = 1 ; j <= n ; j ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
            if(i == j)f[i][j] = 0;
            else f[i][j] = 0x3f3f3f3f;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b] = min(f[a][b], c);
    }
    floyd();
    while(k --)
    {
        int a, b;
        cin >> a >> b;
        if(f[a][b] > 0x3f3f3f3f / 2)cout << "impossible" << endl;
        else cout << f[a][b] << endl;
    }
    return 0;
}