问题抽象&时间复杂度分析

图中节点数 -> n
图中边数量 -> m
单源无负权边最短路 -> dijkstra 朴素版 O(n * m) 堆优化版本 O()
单源有负权边最短路 -> bellman-ford spfa
多源汇的最短路问题 -> floyd

单源无负权边最短路 dijkstra

朴素版本【适用于稠密图】

dijkstra 算法流程
维护一个目前已发现最短路的节点集合S
for i = 1:n
// 一次循环找到未加入集合S的最短dist[k] 加入集合S O(n)
// 适用dist[k]更新不在集合S中的节点的最短距离dist[t] O(n) 一个节点最多往外有n条边

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int g[N][N], dist[N];
bool st[N];
int n, m;

bool dijkstra () {
    memset (dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        st[t] = true;
        for (int j = 1; j <= n; j++) {
            if (!st[j]) dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    return dist[n] < 0x3f3f3f3f;
}

int main () {
    cin >> n >> m;
    memset (g, 0x3f, sizeof g);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    if (dijkstra()) cout << dist[n];
    else cout << -1;
    return 0;
}

堆优化版本

堆优化版本思路 -> 将找最短dist[k]的过程简化成O(lg n)
算法流程
while 堆不空
// 弹出堆顶元素 check是否未加入过S集合如果是将其加入S集合
// 根据边关系更新与新节点相连的其他节点的最短路 dist

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

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

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

bool dijkstra () {
    memset (dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> queue;
    dist[1] = 0;
    queue.push({0, 1});
    // 迭代条件跟朴素版不一致 不在是 1 -> n 次循环
    while (queue.size()) {
        auto t = queue.top();
        queue.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        // cout << "vertex = " << ver << " dist = " << distance << endl;
        st[ver] = true;
        for (int j = h[ver]; j != -1; j = ne[j]) {
            // 节点编号k 边权重为 w[j] 
            int k = e[j];
            if (!st[k] && dist[k] > distance + w[j]) {
                dist[k] = distance + w[j];
                queue.push({dist[k], k});
            }
        }
    }
    return dist[n] < 0x3f3f3f3f;
}

int main () {
    cin >> n >> m;
    memset (h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (dijkstra()) cout << dist[n];
    else cout << -1;
    return 0;
}

带负权图的最短路径

最多经过k条边的最短路径 bellman-ford 算法

bellman-ford 算法流程
for 1->k:
//拷贝上一次的dist数组存在backup数组中
for j : 1->m:
//对所有的m条边分别尝试更新dist[end] 使用的变量需要是backup数组中的
//dist[end] = min(dist[end], backup[start] + w)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
struct edge {
    int a, b, c;
}edges[N];
int dist[N], backup[N];
int n, m, k;


bool bellman_ford () {
    memset (dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        // 必须有一个backup数组承接上一轮次的dist结果 防止套娃重复刷新
        memcpy (backup, dist, sizeof dist);
        for (int j = 1; j <= m; j++) {
            int start = edges[j].a, end = edges[j].b, weight = edges[j].c;
            dist[end] = min(dist[end], backup[start] + weight);
        }
    }
    return dist[n] < 0x3f3f3f3f / 2;
}

int main () {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    if (bellman_ford()) cout << dist[n];
    else cout << "impossible";
    return 0;
}

spfa算法

spfa 算法流程使用一个队列优化bellman-ford算法将能够引起后续dist距离变小的节点加入队列从而优化时间复杂度
st数组表征节点是否在队列内初始时只把源点入队
while hh <= tt 队列不空
// 取出队头
// 尝试更新队头元素对应的后续节点的dist距离
for 队头节点的后续节点
如果可以更新dist距离更新距离
在此基础上如果没入队入队

#include <iostream>
#include <cstring>
#include <algorithm>

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

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

bool spfa () {
    memset (dist, 0x3f, sizeof dist);
    int hh = 0, tt = -1;
    q[++tt] = 1;
    dist[1] = 0;
    st[1] = true;
    while (hh <= tt) {
        auto i = q[hh++];
        st[i] = false;
        for (int j = h[i]; j != -1; j = ne[j]) {
            auto k = e[j];
            if (dist[k] > dist[i] + w[j]) {
                dist[k] = dist[i] + w[j];
                if (!st[k]) {
                    q[++tt] = k;
                    st[k] = true;
                }
            }
        }
    }
    return dist[n] < 0x3f3f3f3f / 2;
}

int main () {
    cin >> n >> m;
    memset (h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (spfa()) cout << dist[n];
    else cout << "impossible";
    return 0;
}