Dijkstra算法

可以求起点 S 到其他点的最短路径，时间复杂度为 O(n²)
例： 找 1 到 n 的最短路径，如果不存在输出 −1

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

using namespace std;
const int INF = 5e6;

const int N = 510;

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

int dijkstra(int s)
{
    for(int i=1; i<=n; ++i)
          dist[i] = INF;
    dist[s] = 0;

    for (int i = 0; i < n - 1; i ++ ) // 对于n个点的图，最多做n-1次更新 
    {
        int t = -1; // 找一个 dist[t]是全局最小的dist， 且没有被标记过 
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;  

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == INF) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m); //n个点， m条边 

    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=n; ++j) {
            if(i==j)    g[i][j]=0;
            else g[i][j] = INF;
        }
    }
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        g[a][b] = min(g[a][b], c); //防止有重边 
    }

    printf("%d\n", dijkstra(1));

    return 0;
}

SPFA

时间复杂度不稳定，为 O(km)， k 为常数。 最坏情况（网格图）：O(n∗m) 。

void spfa() {
    for(int i=1; i<=52; ++i) {
        dist[i] = INF;
        vis[i] = 0;
    }
    queue<int> q;
    int x = 52;
    q.push(x);
    vis[x] = 1;
    dist[52] = 0;
    while(!q.empty()) {
        x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i=head[x]; i!=-1; i=edge[i].nxt) {
            int v = edge[i].to;
            int w = edge[i].val;
            if(dist[v] > dist[x]+w) {
                dist[v] = dist[x]+w;
                if(!vis[v]){
                    mark[v]++;
                    q.push(v);
                    vis[v] = 1;
                }

            }
        }
    }
}

因为在 n 个点的图中，一个点最多被更新 n−1 次。 所以当一个点的更新次数超过 n−1 时，说明存在负环。

拓扑排序

在有向无环图中（DAG）中，拓扑排序可以 O(n) 的复杂度内访问所有的节点。

void Toporder() {
    for(int i=1; i<=n; ++i) {
        if(!indegree[i]) {
            cost[i] = 100;
            ans += cost[i];
            que.push(i);
        }
    }
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        for(int i=0; i<mp[x].size(); ++i) {
            int y = mp[x][i];
            cost[y] = cost[x] + 1;
            indegree[y]--;
            cnt--; //总度数减一，若队列为空时，总度数不为0，则表示图中有环
            if(!indegree[y]) {
                ans += cost[y];
                que.push(y);
            }
        }
    }
}

并查集

查找

普通版： 每次查找根结点的时间复杂度最坏都是 O(n)

int Find(int x) {
    while(x!=bin[x]) 
        x=bin[x];
    return x;
}

非递归版路径压缩：

int Find(int x) { // 非递归版的路径压缩 
    int r = x;
    while(r != bin[r])
            r = bin[r];
    while(x != r) {
        int t = bin[x];
        bin[x] = r;
        x = t;
    }
    return  x; 
}

递归版路径压缩：

int Find(int x) {
    if(x==bin[x])    return x;
    return bin[x] = Find(bin[x]);
}

合并

void merge(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if(fx!=fy) 
        bin[fy] = fx;
}

最小生成树

prim

时间复杂度 O(n²)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
const int INF = 1e9+10;
int n,mp[maxn][maxn], ans=0, dist[maxn], vis[maxn];

void prim()
{
    for(int i=1; i<=n; ++i) {
        dist[i] = mp[1][i];
        vis[i] = 0;
    }
     dist[1] = 0;
     vis[1] = 1;
     for(int i=1; i<=n-1; ++i) {
         int t = -1;
         for(int j=2; j<=n; ++j) {
             if(!vis[j] && (t==-1 || dist[t]>dist[j])) 
                 t=j;
         }
         ans += dist[t]; //ans表示最小生成树的边权值之和 
         vis[t] = 1;
         for(int j=1; j<=n; ++j) {
             if(dist[j] > mp[t][j])
                   dist[j] = mp[t][j];
         }  
     }
    printf("%d\n", ans);    
}

int main()
{
     int m;
     scanf("%d%d", &n, &m);
     for(int i=1; i<=n; ++i) {
         for(int j=1; j<=n; ++j) {
             if(i==j) mp[i][j]=0;
             else mp[i][j] = INF;
         }
     }
     for(int i=1; i<=m; ++i) {
         int x, y, z;
         scanf("%d%d%d", &x, &y, &z);
         mp[x][y] = z;    mp[y][x] = z;
      }
      prim();
    return 0;
}