最短路

Bellman-Ford

时间复杂度$O(nm)$

struct Edge {
    int x, y, v;
}edge[10010];//存边
int n, m, k;
int dis[5010];//dis[i]表示从s到i的最短距离
int pre[5010];//记录连接该节点的上一个节点
int c[5010];
void Bellman(int s,int t) {//最多迭代n-1轮
    memset(dis, 127, sizeof(dis));
    memset(pre, 0, sizeof(pre));
    dis[s] = 0;
    while (true) {
        bool ok = false;//记录在当前的迭代过程中是否遍历，若没有，循环结束
        for (int i = 1; i <= m; i++) {
            int x = edge[i].x, y = edge[i].y, v = edge[i].v;
            if (dis[x] < 1 << 30) {
                if (dis[x] + v < dis[y]) {
                    dis[y] = dis[x] + v;
                    pre[y] = x;
                    ok = true;
                }
            }
        }
        if (!ok) break;
    }
    if (dis[t] < 1 << 30) {
        printf("%d\n", dis[t]);
        /*输出从s到t的最短路，用c存放
        int l = 0;
        for (int i = t; i != s; i=pre[i]) {
            c[++l] = i;
        }
        c[++l] = s;
        for (int i = l; i >= 1; i--) cout << c[i] << " \n"[i == 1];
        */
    }
    else printf("-1\n");
}
void solve() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        edge[i].x = x, edge[i].y = y, edge[i].v = v;
    }
    while (k--) {
        int x, y;
        scanf("%d%d", &x, &y);
        Bellman(x, y);
    }
}

S P F A

把每一轮中新更新的节点存入队列，在每一次迭代中只考虑这些新更新的点，从而达到优化的目的，但在最坏的情况下，时间复杂度依然是$O(nm)$

vector<pair<int, int> >edge[5001];//存边
int n, m, k;
int dis[5010];//dis[i]表示从s到i的最短距离
bool b[5010];//记录当前队列里是否有该元素，如果有，说明不用放入队列，否则放入
int q[5000001];//存放队列,注意数组范围
void SPFA(int s,int t) {
    memset(dis, 127, sizeof(dis));
    memset(b, false, sizeof(b));
    dis[s] = 0;
    b[s] = true;
    int front = 1, rear = 1;//front表示队头，rear表示队尾
    q[rear] = s;//此时队列中只有s这一个元素
    while (front<=rear) {
        int x = q[front];
        ++front;
        b[x] = false;
        for (auto i : edge[x]) {
            if (dis[x] + i.second < dis[i.first]) {//此时不用判断边权是否为无穷大，因为放入队列的元素一定有边
                dis[i.first] = dis[x] + i.second;//即dis[y]=dis[x]+v
                if (!b[i.first]) {//如果y不在队列中，就放入队列
                    q[++rear] = i.first;
                    b[i.first] = true;
                }
            }
        }
    }
    if (dis[t] < 1 << 30) {
        printf("%d\n", dis[t]);
    }
    else printf("-1\n");
}
void solve() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        edge[x].push_back(make_pair(y, v));
    }
    while (k--) {
        int x, y;
        scanf("%d%d", &x, &y);
        SPFA(x, y);
    }
}

Dijkstra

在每一轮中，将离起点最近的（dis最小，不能是无穷大）的还不在C中的顶点加入C，并且用这个点连出去的边通过松弛操作尝试更新其他点的dis,当终点或没有点加入C时，算法结束。时间复杂度为$O(n^2+m)$

朴素写法：

struct Node {
    int y, v;
    Node(int _y, int _v) { y = _y, v = _v; }
};
vector<Node>edge[N + 1];
int n, m, dis[N + 1];
bool b[N + 1];
​
int Dijkstra(int s, int t) {
    memset(b, false, sizeof(b));
    memset(dis, 127, sizeof(dis));
    dis[s] = 0;
    while (true) {
        int x = -1;
        for (int i = 1; i <= n; i++) {
            if (!b[i] && dis[i] < 1 << 30) {
                if (x == -1 || dis[i] < dis[x])
                    x = i;
            }
        }
        if (x == t || x == -1) break;
        b[x] = true;
        for (auto i : edge[x]) {
            dis[i.y] = min(dis[i.y], dis[x] + i.v);
        }
    }
    return dis[t];
}

我们注意到，每次我们都要进行一个找最小的操作，那么我们完全可以通过优先队列(priority_queue)来 找最小，可以将时间复杂度优化至$O((n+m)logn)$

struct Edge { int y, v; };
vector<Edge> edge[MAXN];
int n;
int dis[MAXN];
//pair是一个点对:(first, second)
//在这里我们将first存为dis(v)的值，second存v。
//STL中的优先队列会先根据first来排序，若first相同再按second排序。
void Dijkstra(int s) {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        pair<int, int> p = q.top(); q.pop();
        int v = p.second;
        if (dis[v] < p.first) continue; //此时不是最短路
        //松弛
        for (int i = 0; i < edge[v].size(); i++) {
            Edge e = edge[v][i];
            if (dis[e.y] > dis[v] + e.v) {
                dis[e.y] = dis[v] + e.v;
                q.push(make_pair(dis[e.y], e.y));
            }
        }
    }
}

要注意Dijkstra只能跑非负权的图，如果边权有负的要用spfa

Floyd

int n, m, q, f[301][301];
void solve() {
    scanf("%d%d%d", &n, &m, &q);
    memset(f, 127, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        f[x][y] = z;
    }
    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[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        int s, t;
        scanf("%d%d", &s, &t);
        if (f[s][t] < 1 << 30) printf("%d\n", f[s][t]);
        else printf("-1\n");
    }
}