fordbellmanqueue.cpp

Bài toán

cho đồ thị n đỉnh, m cạnh, tìm đường đi ngắn nhất từ u đến v.

Độ phức tạp

tiến tới O(nm)

tuy nhiên thực tế cho thấy Ford Bellman queue vòng nhanh hơn Dijkstra Heap (dùng priority queue) trong nhiều trường hợp.

#include <stdio.h>

#include <queue>

using namespace std;

#define X first

#define Y second

typedef pair<int, int> ii;

vector<ii> a[230997];

int n, m;

int d[230997];

bool inqueue[230997];

void bellman(int u) {

    queue<int> qu;

    for (int i = 1; i <= n; i++)

        d[i] = 1000111000;

    d[u] = 0;

    qu.push(u);

    inqueue[u] = true;

    while (qu.size()) {

        u = qu.front();

        inqueue[u] = false;

        qu.pop();

        for (int i = 0; i < a[u].size(); i++) {

            int v = a[u][i].Y;

            int uv = a[u][i].X;

            if (d[v] > d[u] + uv) {

                d[v] = d[u] + uv;

                if (!inqueue[v]) {

                    qu.push(v);

                    inqueue[v] = true;

                }

            }

        }

    }

}

int main() {

    int u, v;

    scanf("%d%d%d%d", &n, &m, &u, &v);

    u++;

    v++;

    while (m--) {

        int p, q, w;

        scanf("%d%d%d", &p, &q, &w);

        p++;

        q++;

        a[p].push_back(ii(w, q));

        a[q].push_back(ii(w, p));

    }

    bellman(u);

    printf("%d\n", d[v]);

}

Nhận xét

Khá giống Dijkstra Heap, tuy nhiên, bằng một số thay đổi, ta có thể xác định được chu trình âm.

Cảm ơn anh Hy Trường Sơn đã giúp em hoàn thiện bài viết này.