图论相关算法模板

许多书上的算法可能是为了易懂，显得比较冗长，这里尽可能给出简洁的实现：

Bellman-Ford最短路算法

注意，要求不能有负圈

struct Edge { int from, to, cost; };
Edge es[maxE];
int V, E;

int d[maxV];
int V, E;

void bellmanFord(int s) {
    fill(d, d + V, inf);
    d[s] = 0;
    while (1) {
        bool update = 0;
        for (int i = 0; i < E; ++i) {
            Edge e = es[i];
            if (d[e.from] != inf
                    && d[e.from] + e.cost < d[e.to]) {
                d[e.to] = d[e.from] + e.cost;
                update = 1;
            }
        }
        if (!update)
            break;
    }
}

Bellman-Ford也可以用来判负圈。因为最短路不会经过一个点2次，所以update操作最多执行|V|-1次。若操作真的到了V-1还有更新，说明有负圈。为什么d要初始化为0，这个待思考。

struct Edge { int from, to, cost; };
Edge es[maxE];
int V, E, d[maxV];

bool hasNegativeLoop() {
    fill(d, d + V, 0);
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < E; ++j) {
            Edge e = es[j];
            if (d[e.from] != inf
                    && d[e.from] + e.cost < d[e.to]) {
                d[e.to] = d[e.from] + e.cost;
                if (i == V - 1)
                    return 1;
            }
        }
    }
    return 0;
}

Dijkstra最短路算法

关键在于2点：

1. 找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离
2. 此后不需要再关心1中的“最短距离已经确定的顶点”

朴素的Dijkstra算法有：

int cost[maxV][maxV];
int V, d[maxV];
bool used[maxV];

void dijkstra(int s) {
    fill(d, d + V, inf);
    fill(used, used + V, 0);
    d[s] = 0;

    while (1) {
        int u = -1;
        for (int i = 0; i < V; ++i)
            if (!used[i] && (u == -1 || d[i] < d[u]))
                u = i;
        if (u == -1)
            break;
        used[u] = 1;
        for (int i = 0; i < V; ++i)
            d[i] = min(d[i], d[u] + cost[u][i]);
    }
}

但是这里找离s最近的点的时候，每次都要一个for循环扫，效率较低，也使得朴素的dijkstra算法复杂度为O(|V|^2)，由于要找最小值，可以想到用最小堆来找。找到距离s最小的点之后，如果它是最短距离已经确定的顶点，ok，拿来更新，则有改进版实现，插入的边的次数是O(|E|)次，找最近点耗费O(log|V|)，所以复杂度是O(|E|*log|V|)：

struct Edge { int to, cost; };
typedef pair<int, int> P;
int V, d[maxV];
vector<Edge> G[maxV];

void dijkstra(int s) {
    fill(d, d + V, inf);
    d[s] = 0;

    priority_queue<P, vector<P>, greater<P> > Q;
    Q.push(P(0, s));

    while (!Q.empty()) {
        P p = Q.top();
        Q.pop();
        int v = p.second;
        if (d[v] != p.first)
            continue;

        for (int i = 0; i < G[v].size(); ++i) {
            Edge e = G[v][i];
            if (d[v] + e.cost < d[e.to]) {
                d[e.to] = d[v] + e.cost;
                Q.push(P[d[e.to], e.to]);
            }
        }
    }
}