Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 28.632 phút đọc

Đường đi ngắn nhất và cây khung

Sau bài này bạn sẽ làm được

  • Cài Dijkstra với hàng đợi ưu tiên
  • Biết vì sao Dijkstra hỏng với trọng số âm
  • Cài Floyd-Warshall và hiểu vì sao k phải ở vòng ngoài cùng
  • Cài Kruskal với union-find có nén đường

Bốn thuật toán đường đi ngắn nhất và hai thuật toán cây khung nhỏ nhất. Mỗi cái mạnh ở một điều kiện khác nhau, và biết cái nào dùng được khi nào quan trọng hơn nhớ được mã.

#Dijkstra

Dijkstra
Tìm đường đi ngắn nhất từ một đỉnh nguồn tới mọi đỉnh khác, với điều kiện mọi trọng số không âm. Chiến lược tham lam: luôn mở rộng đỉnh có khoảng cách tạm tính nhỏ nhất trong số các đỉnh chưa chốt.
dijkstra.c
#include <limits.h>
#include <stdlib.h>

typedef struct { int dinh; long kc; } Muc;

/* Heap nhỏ nhất theo trường kc, cùng mẫu Bài 23.4. */

/* Trả về 0 nếu ổn, -1 nếu hết bộ nhớ.
   Ghi khoảng cách vào kc, đỉnh trước vào cha.
   O((V + E) log V) với heap nhị phân. */
int dijkstra(const DoThi *g, int nguon, long *kc, int *cha)
{
    Heap h;

    heap_khoi_tao(&h);

    for (size_t i = 0; i < g->V; ++i) { kc[i] = LONG_MAX; cha[i] = -1; }

    kc[nguon] = 0;

    if (heap_push(&h, (Muc){ nguon, 0 }) != 0) { heap_huy(&h); return -1; }

    while (!heap_rong(&h)) {
        Muc m;

        heap_pop(&h, &m);

        /* Mục cũ đã lỗi thời, bỏ qua. Đây là cách tránh phải
           cài thao tác giảm khóa trong heap. */
        if (m.kc > kc[m.dinh]) continue;

        size_t u = (size_t)m.dinh;

        for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
            int  v  = g->ke[i];
            long nd = kc[u] + g->trong_so[i];

            if (nd < kc[v]) {
                kc[v]  = nd;
                cha[v] = (int)u;

                if (heap_push(&h, (Muc){ v, nd }) != 0) {
                    heap_huy(&h);

                    return -1;
                }
            }
        }
    }

    heap_huy(&h);

    return 0;
}

Vết trên một đồ thị nhỏ

Do thi 6 dinh, trong so:
  0-1: 7    0-2: 9    0-5: 14
  1-2: 10   1-3: 15
  2-3: 11   2-5: 2
  3-4: 6
  4-5: 9

Buoc  Chot dinh  kc sau khi chot
  1   0 (kc 0)   [0, 7, 9, inf, inf, 14]
  2   1 (kc 7)   [0, 7, 9,  22, inf, 14]
  3   2 (kc 9)   [0, 7, 9,  20, inf, 11]    2->5 cho 11 < 14
  4   5 (kc 11)  [0, 7, 9,  20,  20, 11]
  5   3 (kc 20)  [0, 7, 9,  20,  20, 11]    3->4 cho 26, khong tot hon
  6   4 (kc 20)  xong

Ket qua: 0->0 = 0,  0->1 = 7,  0->2 = 9,
         0->3 = 20, 0->4 = 20, 0->5 = 11
terminal
gcc -std=c17 -Wall -Wextra dijkstra.c heap.c main.c -o t && ./t
dinh   kc   duong di
   0    0   0
   1    7   0 -> 1
   2    9   0 -> 2
   3   20   0 -> 2 -> 3
   4   20   0 -> 2 -> 5 -> 4
   5   11   0 -> 2 -> 5
Cấu trúc ưu tiênĐộ phức tạpKhi nào dùng
Mảng, quét tìm nhỏ nhấtO(V bình phương)Đồ thị dày, E gần V bình phương
Heap nhị phânO((V + E) log V)Đồ thị thưa, lựa chọn mặc định
Heap FibonacciO(E + V log V)Chỉ tốt về lý thuyết, hằng số quá lớn
Mảng theo trọng sốO(V + E + W)Trọng số nguyên nhỏ, gọi là Dial
terminal
./do-dijkstra
do thi thua: 1000000 dinh, 5000000 canh
  mang quet    : khong doi noi
  heap nhi phan: 2.412 s

do thi day: 5000 dinh, 12500000 canh
  mang quet    : 0.184 s
  heap nhi phan: 1.842 s   <- CHAM hon

voi do thi day, mang quet thang vi khong ton chi phi heap

#Vì sao Dijkstra hỏng với trọng số âm

Do thi:
   0 --(5)--> 1
   0 --(2)--> 2
   2 --(-4)-> 1

Dijkstra tu 0:
  Chot 0, cap nhat kc[1] = 5, kc[2] = 2
  Chot 2 vi kc nho nhat la 2, cap nhat kc[1] = min(5, 2 + (-4)) = -2
  Chot 1 voi kc = -2

  O day may man dung. Nhung doi thu tu:

Do thi:
   0 --(2)--> 1
   0 --(5)--> 2
   1 --(-4)-> 2

Dijkstra tu 0:
  Chot 0, kc[1] = 2, kc[2] = 5
  Chot 1 vi 2 < 5, cap nhat kc[2] = 2 + (-4) = -2
  Chot 2 voi kc = -2

  Van dung. Van de that su xay ra khi dinh da CHOT bi cai thien: */

#Bellman-Ford

bellman-ford.c
#include <limits.h>

/* Cho phép trọng số ÂM. Phát hiện chu trình âm.
   Trả về 0 nếu ổn, 1 nếu có chu trình âm tới được từ nguồn.
   O(V nhân E). */
int bellman_ford(size_t V, const Canh *e, size_t E, int nguon, long *kc)
{
    for (size_t i = 0; i < V; ++i) kc[i] = LONG_MAX;

    kc[nguon] = 0;

    /* Lặp V-1 lượt. Sau lượt k, kc[v] đúng với mọi đường
       dùng nhiều nhất k cạnh. Đường ngắn nhất không có chu trình
       nên dùng nhiều nhất V-1 cạnh. */
    for (size_t lan = 0; lan + 1 < V; ++lan) {
        int co_doi = 0;

        for (size_t i = 0; i < E; ++i) {
            if (kc[e[i].u] == LONG_MAX) continue;      /* chưa tới được */

            long nd = kc[e[i].u] + e[i].w;

            if (nd < kc[e[i].v]) {
                kc[e[i].v] = nd;
                co_doi     = 1;
            }
        }

        if (!co_doi) break;      /* đã ổn định, dừng sớm */
    }

    /* Lượt thứ V: nếu còn cải thiện được thì có chu trình âm */
    for (size_t i = 0; i < E; ++i) {
        if (kc[e[i].u] == LONG_MAX) continue;

        if (kc[e[i].u] + e[i].w < kc[e[i].v]) return 1;
    }

    return 0;
}
Chu trình âm
Một chu trình có tổng trọng số âm. Nếu tới được từ nguồn thì không tồn tại đường đi ngắn nhất, vì đi vòng quanh chu trình đó mãi làm độ dài giảm vô hạn. Bellman-Ford phát hiện được, Dijkstra thì không.
terminal
./bellman-ford chu-trinh-am.txt
do thi: 0->1 (1), 1->2 (-3), 2->1 (1)

chu trinh 1 -> 2 -> 1 co tong trong so -2
PHAT HIEN CHU TRINH AM, khong co duong ngan nhat
DijkstraBellman-FordFloyd-Warshall
Trọng số âmKhôngCóCó
Phát hiện chu trình âmKhôngCóCó
Từ một nguồn hay mọi cặpMột nguồnMột nguồnMọi cặp
Độ phức tạpO(E log V)O(V nhân E)O(V lập phương)
Bộ nhớO(V)O(V)O(V bình phương)
Số dòng mãKhoảng 30Khoảng 20Khoảng 8

#Floyd-Warshall

floyd.c
/* Duong di ngan nhat giua MOI cap dinh.
   d la mang phang V x V, d[i*V+j] la trong so canh i->j,
   hoac INF neu khong co canh, va 0 khi i == j. */
void floyd_warshall(size_t V, long *d, long INF)
{
    for (size_t k = 0; k < V; ++k)              /* k PHAI o vong NGOAI CUNG */
        for (size_t i = 0; i < V; ++i) {
            if (d[i * V + k] == INF) continue;  /* cat tia, i khong toi duoc k */

            for (size_t j = 0; j < V; ++j) {
                if (d[k * V + j] == INF) continue;

                long qua_k = d[i * V + k] + d[k * V + j];

                if (qua_k < d[i * V + j])
                    d[i * V + j] = qua_k;
            }
        }
}
truy-vet.c
/* Giu them mang tiep de dung lai duong di. */
for (size_t i = 0; i < V; ++i)
    for (size_t j = 0; j < V; ++j)
        tiep[i * V + j] = (d[i * V + j] != INF) ? (int)j : -1;

for (size_t k = 0; k < V; ++k)
    for (size_t i = 0; i < V; ++i)
        for (size_t j = 0; j < V; ++j)
            if (d[i * V + k] != INF && d[k * V + j] != INF &&
                d[i * V + k] + d[k * V + j] < d[i * V + j]) {
                d[i * V + j]    = d[i * V + k] + d[k * V + j];
                tiep[i * V + j] = tiep[i * V + k];      /* buoc dau tien */
            }

/* In duong di tu u toi v: */
void in_duong(const int *tiep, size_t V, int u, int v)
{
    if (tiep[u * V + v] == -1) { printf("khong co duong"); return; }

    printf("%d", u);

    while (u != v) {
        u = tiep[u * V + v];

        printf(" -> %d", u);
    }
}
terminal
./do-floyd
     V   floyd-warshall   dijkstra V lan
   100         0.002 s         0.004 s
   500         0.184 s         0.098 s
  1000         1.410 s         0.412 s
  2000        11.200 s         1.840 s

do thi thua thi chay Dijkstra V lan nhanh hon nhieu.
floyd chi thang khi do thi RAT day hoac co trong so am.

#Union-find

Union-find
Cấu trúc quản lý một họ các tập hợp rời nhau, với hai thao tác: hỏi hai phần tử có cùng tập không, và gộp hai tập. Với hai tối ưu nén đường và gộp theo hạng, mỗi thao tác gần như O(1).
union-find.c
#include <stdlib.h>

typedef struct {
    int    *cha;
    int    *hang;      /* cận trên của chiều cao cây */
    size_t  n;
} UF;

int uf_tao(UF *u, size_t n)
{
    u->cha  = malloc(n * sizeof *u->cha);
    u->hang = calloc(n, sizeof *u->hang);

    if (u->cha == NULL || u->hang == NULL) {
        free(u->cha); free(u->hang);

        return -1;
    }

    for (size_t i = 0; i < n; ++i) u->cha[i] = (int)i;   /* mỗi phần tử một tập */

    u->n = n;

    return 0;
}

/* Tìm đại diện của tập chứa x, có NÉN ĐƯỜNG.
   Bản lặp, không sợ tràn ngăn xếp với cây sâu. */
int uf_tim(UF *u, int x)
{
    int goc = x;

    while (u->cha[goc] != goc) goc = u->cha[goc];      /* tìm gốc */

    while (u->cha[x] != goc) {                          /* nén đường */
        int ke = u->cha[x];

        u->cha[x] = goc;
        x         = ke;
    }

    return goc;
}

/* Gộp hai tập. Trả về 1 nếu thật sự gộp, 0 nếu đã cùng tập. */
int uf_gop(UF *u, int a, int b)
{
    a = uf_tim(u, a);
    b = uf_tim(u, b);

    if (a == b) return 0;

    /* GỘP THEO HẠNG: treo cây thấp vào cây cao, để không tăng chiều cao */
    if (u->hang[a] < u->hang[b]) { int t = a; a = b; b = t; }

    u->cha[b] = a;

    if (u->hang[a] == u->hang[b]) ++u->hang[a];

    return 1;
}

#Kruskal và Prim

Cây khung nhỏ nhất
Tập con các cạnh nối mọi đỉnh, không tạo chu trình, và có tổng trọng số nhỏ nhất. Với đồ thị liên thông V đỉnh, nó luôn có đúng V - 1 cạnh.
kruskal.c
#include <stdlib.h>

typedef struct { int u, v; long w; } Canh;

static int theo_trong_so(const void *pa, const void *pb)
{
    const Canh *a = pa, *b = pb;

    return (a->w > b->w) - (a->w < b->w);
}

/* Trả về tổng trọng số cây khung, hoặc -1 nếu đồ thị không liên thông.
   Ghi các cạnh được chọn vào ra nếu ra khác NULL.
   O(E log E) do phép sắp xếp. */
long kruskal(Canh *e, size_t E, size_t V, Canh *ra)
{
    UF u;

    if (uf_tao(&u, V) != 0) return -1;

    qsort(e, E, sizeof *e, theo_trong_so);      /* THAM LAM: cạnh nhẹ trước */

    long   tong = 0;
    size_t dem  = 0;

    for (size_t i = 0; i < E && dem + 1 < V; ++i)
        if (uf_gop(&u, e[i].u, e[i].v)) {       /* không tạo chu trình */
            if (ra != NULL) ra[dem] = e[i];

            tong += e[i].w;
            ++dem;
        }

    uf_huy(&u);

    return (dem + 1 == V) ? tong : -1;
}
Vet tren do thi 6 dinh o muc Dijkstra:

Canh sap theo trong so:
  (2,5,2) (3,4,6) (0,1,7) (4,5,9) (0,2,9) (1,2,10) (2,3,11) (0,5,14) (1,3,15)

  (2,5,2)  : 2 va 5 khac tap  -> LAY.  tong 2,  tap {2,5}
  (3,4,6)  : khac tap         -> LAY.  tong 8,  tap {3,4}
  (0,1,7)  : khac tap         -> LAY.  tong 15, tap {0,1}
  (4,5,9)  : 4 thuoc {3,4}, 5 thuoc {2,5}, khac -> LAY. tong 24, {2,3,4,5}
  (0,2,9)  : 0 thuoc {0,1}, 2 thuoc {2,3,4,5}   -> LAY. tong 33, tat ca
  da du 5 canh = V - 1, dung

Tong trong so cay khung: 33
terminal
gcc -std=c17 -Wall -Wextra kruskal.c union-find.c main.c -o t && ./t
canh trong cay khung:
  2 - 5   trong so  2
  3 - 4   trong so  6
  0 - 1   trong so  7
  4 - 5   trong so  9
  0 - 2   trong so  9

tong trong so: 33
so canh: 5 = V - 1   dung

Prim

prim.c
#include <limits.h>

/* Mo rong cay tu MOT dinh, moi lan them canh nhe nhat noi cay
   voi mot dinh chua thuoc cay. Dung heap nho nhat.
   O(E log V). */
long prim(const DoThi *g, int nguon)
{
    long *khoa    = malloc(g->V * sizeof *khoa);
    int  *trong   = calloc(g->V, sizeof *trong);
    Heap  h;

    if (khoa == NULL || trong == NULL) { free(khoa); free(trong); return -1; }

    heap_khoi_tao(&h);

    for (size_t i = 0; i < g->V; ++i) khoa[i] = LONG_MAX;

    khoa[nguon] = 0;
    heap_push(&h, (Muc){ nguon, 0 });

    long   tong = 0;
    size_t dem  = 0;

    while (!heap_rong(&h)) {
        Muc m;

        heap_pop(&h, &m);

        if (trong[m.dinh]) continue;      /* muc loi thoi */

        trong[m.dinh] = 1;
        tong         += m.kc;
        ++dem;

        size_t u = (size_t)m.dinh;

        for (size_t i = g->dinh[u]; i < g->dinh[u + 1]; ++i) {
            int  v = g->ke[i];
            long w = g->trong_so[i];

            if (!trong[v] && w < khoa[v]) {
                khoa[v] = w;
                heap_push(&h, (Muc){ v, w });
            }
        }
    }

    heap_huy(&h);
    free(khoa);
    free(trong);

    return (dem == g->V) ? tong : -1;
}
KruskalPrim
Ý tưởngSắp cạnh, lấy cạnh nhẹ không tạo chu trìnhMở rộng cây từ một đỉnh
Cấu trúc phụUnion-findHeap nhỏ nhất
Độ phức tạpO(E log E)O(E log V)
Với đồ thị thưaThắngNgang
Với đồ thị dàyThua vì phải sắp E cạnhThắng, nhất là bản dùng mảng O(V bình phương)
Đồ thị không liên thôngCho rừng khung, vẫn dùng đượcChỉ được thành phần chứa nguồn
Dễ càiDễ hơn nếu đã có union-findDễ nếu đã có Dijkstra
terminal
./do-kruskal-prim
do thi thua: 1000000 dinh, 5000000 canh
  kruskal : 3.412 s
  prim    : 4.108 s

do thi day: 5000 dinh, 12500000 canh
  kruskal : 8.412 s   (ton nhieu thoi gian sap xep)
  prim    : 3.184 s
  prim mang O(V^2) : 0.184 s

Tự làm thử

  1. Cài Dijkstra với heap và kiểm vết trên đồ thị sáu đỉnh trong bài, xác nhận kết quả 0 7 9 20 20 11.
  2. Dựng đồ thị bốn đỉnh có cạnh âm trong bài, chạy Dijkstra và Bellman-Ford, rồi so kết quả.
  3. Cài Floyd-Warshall, thử ba thứ tự vòng lặp và tìm đồ thị làm hai thứ tự sai cho kết quả khác nhau.
  4. Cài union-find với bốn mức tối ưu và đo mười triệu thao tác cho từng mức.
  5. Cài cả Kruskal và Prim, chạy trên cùng đồ thị và xác nhận tổng trọng số bằng nhau dù tập cạnh có thể khác.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Dijkstra tham lam theo khoảng cách nhỏ nhất, chỉ đúng khi mọi trọng số không âm, và chạy trong O(E log V) với heap.
  • Mẹo bỏ qua mục lỗi thời trong heap thay được thao tác giảm khóa, làm mã ngắn hơn nhiều mà độ phức tạp không đổi.
  • Bellman-Ford chịu được trọng số âm và phát hiện chu trình âm, đổi lại O(V nhân E). Phải kiểm vô cùng trước khi cộng.
  • Floyd-Warshall chỉ tám dòng nhưng k bắt buộc ở vòng ngoài cùng, và O(V lập phương) giới hạn nó ở vài nghìn đỉnh.
  • Union-find với nén đường và gộp theo hạng cho mỗi thao tác gần như O(1), và nó là nền của Kruskal.