Dijkstra

单源汇最短路，要求图上不存在负权边
时间复杂度为 $O((N+M)logN)$

Important

经暴打，使用优先队列的时间更优，因为常数更小，小心被Set卡常哦

优先队列

int d[N];
int st[N];

using pt = pair<int, int>;

void dij(int s, int u)
{
    for (int i = 1; i <= n; i ++) {
        d[i] = inf;//1e9或1e18  不要0x3f,因为不够ll用
        st[i] = false;
    }
    d[s] = 0;
    priority_queue<pt, vector<pt>, greater<pt>> q;
    q.push({d[s], s});
    while (!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (st[x])
            continue;
        st[x] = true;
        for (auto [y, v] : edge[x])
            if (d[y] > d[x] + v)
            {
                d[y] = d[x] + v;
                q.push({d[y], y});
            }
    }
}

Set

vector<pair<int, int>> edge[N];

int n, m, s;
int dist[N];

set<pair<int, int>> q;

void dij(int s){
    memset(dist, 127, sizeof dist);
    dist[s] = 0; q.clear();
    for (int i = 1; i <= n; i ++ ) 
        q.insert(make_pair(dist[i], i));
    while (!q.empty()){
        int x = q.begin()->second;
        q.erase(q.begin());
        if (dist[x] > 1 << 30) break;//无法抵达x
        for (auto [y, v]:edge[x])
            if (dist[y] > dist[x] + v){
                q.erase(make_pair(dist[y], y));
                dist[y] = dist[x] + v;
                q.insert(make_pair(dist[y], y));
            }
    }    
}

分层图

点的状态有k种，并且k较小时，可以使用二维 $[x][j]$ 表示 $nk$ 种状态，这样就可以转化为最短路，跑djk
记得改变转移代码
经实验，nk状态(不建立分层图，队列维护3条信息)比nk点(建立分层图，队列维护2信息)更简便易写。
示例如下：

vector<int> edge[N]; //依情况调整

int n, m, k, a[N];

ll d[N][12];
int st[N][12];

using pt = pair<int, int>;
using ptt = pair<ll, pt>;

void dij()
{
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j <= k; j ++ ) {
            d[i][j] = 1e18, st[i][j] = false;
        }
    priority_queue<ptt, vector<ptt>, greater<ptt>> q;
    d[1][0] = a[1];
    q.push({d[1][0], {1, 0}});
    d[1][1] = 1;
    q.push({d[1][1], {1, 1}});
    while (!q.empty())
    {
        auto [x, j] = q.top().second;
        q.pop();
        if (st[x][j])
            continue;
        st[x][j] = true;
        for (auto y : edge[x]){
            if (d[y][0] > d[x][j] + a[y]){
                d[y][0] = d[x][j] + a[y];
                q.push({d[y][0], {y, 0}});
            }
            if (j < k)
                if (d[y][j + 1] > d[x][j] + 1){
                    d[y][j + 1] = d[x][j] + 1;
                    q.push({d[y][j + 1], {y, j + 1}});
                }
        }
    }
}

void solve(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], edge[i].clear();
    while (m -- ){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dij();
    ll ans = 1e18;
    for (int j = 0; j <= k; j ++ ) ans = min(ans, d[n][j]);
    cout << ans << '\n';
}

Bellman-Ford

Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
由于每轮松弛会使得最短路的边数至少+1，而最短路的边数最多 $n-1$，故最多进行 $n-1$轮松弛操作。
如果第 $n$ 轮循环时仍然存在可以松弛的边，说明从 $S$ 出发，能够抵达一个负环。
时间复杂度为 $O(NM)$

struct Node
{
    int x, y, v;
} edge[M];

int n, m, num = 0;
int dist[N];

bool bf(int s)
{
    memset(dist, 127, sizeof dist);
    dist[s] = 0;
    int cnt = 0;
    for (;;)
    {
        ++cnt;
        bool ok = false;
        for (int i = 1; i <= num; i++)
        {
            auto [x, y, v] = edge[i];
            if (dist[x] < 1 << 30 && dist[y] > dist[x] + v){ //可以到达x && 能松弛 
                dist[y] = dist[x] + v;
                ok = true;
            }
        }
        if (ok && cnt == n) return true;
        if (!ok)
            break;
    }
    return false;
}

Warning

需要注意的是，以 $S$ 点为源点跑Bellman-Ford算法时，如果没有给出存在负环的结果，只能说明从 $S$ 点出发不能抵达一个负环，>不能说明图上不存在负环。

因此需要判断整张图上是否存在负环时，最严谨的做法时设置一个超级源点，向图上每个顶点连一条权值是 $0$ 的边，然后以超级源点为起点跑一遍Bellman-Ford算法

SPFA

Bellman-Ford的优化
很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次松弛。
那么只需要用队列来维护 引起松弛的结点，就只能访问必要的边了。
SPFA也可以判断 $S$ 能否抵达一个负环，只需要记录最短路经过的边数，但至少为 $n$ 条边时，说明从起点 $S$ 抵达一个负环。
时间复杂度最多(被卡)为 $O(NM)$

vector<pair<int, int>> edge[N];

int n, m, s;
int dist[N], b[N], q[N * M], cnt[N];

bool spfa(int s)
{
    memset(dist, 127, sizeof dist);
    memset(b, false, sizeof b);
    dist[s] = 0;
    b[s] = true;

    int front = 1, rear = 0;
    q[++rear] = s;
    while (front <= rear)
    {
        int x = q[front];
        ++front;
        b[x] = false;
        for (auto [y, v] : edge[x])
            if (dist[y] > dist[x] + v)
            {
                dist[y] = dist[x] + v;
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n) return true; //存在负环
                if (!b[y])
                {
                    q[++rear] = y;
                    b[y] = true;
                }
            }
    }
    return false;
}

Floyd

多源汇最短路算法
$f[k][i][j]$ 表示从 $i$ 到 $j$，中间只经过 $1-k$ 的最短路径的长度
考虑转移

不经过 $k$, $f[k-1][i][j]$
经过 $k$, $f[k-1][i][k] + f[k-1][k][j]$

二者取 $min$

void solve() {
    //非空间优化
    for (int k = 1; k <= n; k ++ ) //注意k作为第一维
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j]);

    //空间优化
    for (int k = 1; k <= n; k++) 
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (f[i][k] < 1 << 30 && f[k][j] < 1 << 30)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}