图论-最短路

Dijkstra

求单源最短路

const int N = 1e5+5;
const int M = 2e5+5;
const int inf = 0x3f3f3f3f;
int dis[N], head[N];
bool inq[N];
int cnt;
struct edge {
    int v, w, next; 
}e[M];

void add(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

int main(int argc, char const *argv[])
{
    memset(dis, 0x3f, sizeof(dis));
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0, s});
    dis[s] = 0;
    while (!q.empty()) {
        auto x = q.top();
        q.pop();
        int u = x.second;
        if (inq[u]) continue;
        inq[u] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dis[i] != inf) cout << dis[i] << ' ';
        else cout << INT_MAX << ' ';
    }
    return 0;
}
// input:
// 4 6 1
// 1 2 2
// 2 3 2
// 2 4 1
// 1 3 5
// 3 4 3
// 1 4 4
// output:
// 0 2 4 3

时间复杂度：$O(mlogn)$

反向Dijkstra

有向图，求解从1走到任意n的最短路可以用Dijkstra，如果要再求解从任意n走到1的最短路可以用反向建图的Dijkstra

const int N = 2005;
const int M = 200005;
const int inf = 0x3f3f3f3f;

struct edge{
    int v, w, next;
}e[M];

int head[N], dist[N];
bool inq[N];
int cnt;
void add(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
void Dijkstra(int s) {
    memset(dist, 0x3f, sizeof(dist));
    memset(inq, 0, sizeof(inq));
    q.push({0, s});
    dist[s] = 0;
    while (!q.empty()) {
        auto x = q.top();
        q.pop();
        int u = x.second;
        if (inq[u]) continue;
        inq[u] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            int w = dist[u] + e[i].w;
            if (dist[v] > w) {
                dist[v] = w;
                q.push({w, v});
            }
        }
    }
}
int main(int argc, char const *argv[])
{
    int n, m;
    int u, v, w;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v + n, u + n, w);   // 节点扩展1倍，不更原来的混在一起
    }
    Dijkstra(1);
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res += dist[i];
    }
    Dijkstra(n + 1);
    for (int i = 2 + n; i <= 2 * n; i++) {  // 这里也是扩展的节点
        res += dist[i];
    }
    cout << res;
    return 0;
}
// input:
// 5 10
// 2 3 5
// 1 5 5
// 3 5 6
// 1 2 8
// 1 3 8
// 5 3 4
// 4 1 8
// 4 5 3
// 3 5 6
// 5 4 2
// output:
// 83

最短路计数

如果dist[u]+w>dist[v]，说明v只能从u过来才是最短，所以nums[v]=nums[u]
如果dist[u]+w==dist[v]，说明v多了一种从u过来的最短路，所以nums[v]+=nums[u]

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

const int N = 1000005;
const int M = 2000000;
const int mod = 100003;
struct edge {
    int v, next;
}e[M];
int cnt;
int head[N], dist[N], nums[N];
bool inq[N];
void add(int u, int v) {
    e[++cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
void Dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0, 1});
    dist[1] = 0;
    nums[1] = 1;
    while (!q.empty()) {
        auto x = q.top();
        q.pop();
        int u = x.second;
        if (inq[u]) continue;
        inq[u] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            int w = dist[u] + 1;
            if (dist[v] > w) {
                dist[v] = w;
                nums[v] = nums[u] % mod;
                q.push({w, v});
            }
            else if (dist[v] == w) {
                nums[v] = (nums[v] + nums[u]) % mod;
            }
        }
    }
}
int main(int argc, char const *argv[])
{
    int n, m;
    int u, v;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    Dijkstra();
    for (int i = 1; i <= n; i++) {
        cout << nums[i] << endl;
    }
    return 0;
}

---

Bellman Ford

可以解决负权边的问题，也可以判负环

每次都枚举每一条边，看是否能更新节点，最多枚举n-1次

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

const int N = 10005;
const int M = 5e5+5;

struct edge {
    int u, v, w;
}e[M];
int head[N], dist[N];
int cnt;
void add(int u, int v, int w) {
    e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
}
int n, m, s;
int u, v, w;

void Bellman_Ford() {
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for (int i = 1; i < n; i++) {   // 最多n-1次
        bool flag = false;
        for (int j = 1; j <= cnt; j++) {    // 枚举每一条边
            int u = e[j].u, v = e[j].v, w = e[j].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                flag = true;
            }
        }
        if (!flag) break;   // 说明不再更新，可以退出了
    }
}
int main(int argc, char const *argv[])
{
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    Bellman_Ford();
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << ' ';
    }
    cout << endl;
    return 0;
}

时间复杂度：$O(nm)$

在枚举边的过程中有些边是不需要枚举的，只有刚才被松弛过的点连接的边才能松弛其他的点，所以把松弛过的点放到队列中，枚举些边就够了，即SPFA

---

SPFA

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

const int N = 10005;
const int M = 5e5+5;

struct edge {
    int u, v, w, next;
}e[M];
int cnt;
int dist[N], head[N];
bool inq[N];
void add(int u, int v, int w) {
    e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

int n, m, s;
int u, v, w;

void SPFA(int s) {
    memset(dist, 0x3f, sizeof(dist));
    memset(inq, 0, sizeof(inq));
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    inq[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false; // 出队之后改为false
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            int w = dist[u] + e[i].w;
            if (dist[v] > w) {
                dist[v] = w;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    SPFA(s);
    for (int i = 1; i <= n; i++) {
        if (dist[i] != 0x3f3f3f3f) cout << dist[i] << ' ';
        else cout << 2147483647 << ' ';
    }
    cout << endl;
    return 0;
}

时间复杂度：$O(km)$，最坏情况下是$O(nm)$

如果一个点的入队次数大于等于n，说明有负环

---

Floyd

前面的三种方法都是求单源最短路，floyd可以求各个节点到其他节点的最短路

基本思想是把节点k插入到节点i和节点j之间，看能不能更新i到j的路径长度

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1005;
const int M = 10005;
const int inf = 0x3f3f3f3f;

int G[N][N], pre[N][N], dist[N][N];

int n, m;
int u, v, w;

void Floyd() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = G[i][j];
            if (dist[i][j] != inf && i != j) pre[i][j] = i;
            else pre[i][j] = -1;
        }
    }
    for (int k = 1; k <= n; k++) {  // 把k节点插入到ij之间
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j] = pre[k][j];  // 更新前继节点
                }
            }
        }
    }
}

void findPath(int i, int j) {
    if (pre[i][j] == -1) return;
    findPath(i, pre[i][j]);
    cout << pre[i][j] << "->";
}

int main(int argc, char const *argv[])
{
    memset(G, inf, sizeof(G));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        G[u][v] = min(G[u][v], w);  // 防止重边覆盖
    }
    Floyd();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << dist[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << pre[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            findPath(i, j);
            cout << j << endl;
        }
    }
    return 0;
}
// 4 6
// 1 2 1
// 1 4 4
// 2 4 2
// 3 1 3
// 3 2 5
// 4 3 6

// dist数组：
// 0 1 9 3 
// 11 0 8 2 
// 3 4 0 6 
// 9 10 6 0 

// pre数组：
// -1 1 4 2 
// 3 -1 4 2 
// 3 1 -1 2 
// 3 1 4 -1 

// 最短路径：
// 1->2
// 1->2->4->3
// 1->2->4
// 2->4->3
// 2->4
// 3->1->2->4

时间复杂度：$O(n^3)$