[Thuật toán] Tìm đường đi ngắn nhất Dijkstra, Floyd

Tháng Mười Hai 29, 2014 nguyenvanquan7826 TT Đồ thị 139 responses


Update 25/05/2014: Do một số góp ý của các bạn nên mình đã viết thêm 1 chương trình của thuật toán Dijkstra theo cấu trúc hàm và cũng nhân tiện chỉnh lại chút code cho sáng sủa và chính xác hơn ^^.

Update 27/09/2014: bổ xung code pascal của thuật toán tại đây: http://ideone.com/c7J0dq

Nội dung
Thuật toán Dijkstra
Thuật toán Floyd
Code nâng cao cho cả 2 thuật toán

Update 14/06/2014: Chương trình mô phỏng thuật toán Dijkstra

Trong bài viết này chỉ đề cập tới các thuật toán tìm đường đi ngắn nhất Dijkstra và Floyd, một số thuật ngử liên quan mình sẽ không giải thích hay định nghĩa, các bạn tự tìm hiểu trong sách hoặc trên mạng.

Bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất. Hay nói một cách toán học là:
Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(a,b) từ một đỉnh a cho trước đến một đỉnh b bất kỳ của G và tìm đường đi ngắn nhất từ a đến b.

Như tiêu đề bài viết, chúng ta sẽ tìm hiểu 2 thuật toán để giải quyết bằng cách sử dụng mà trận kề cảu đồ thị(chú ý ta xét trọng số của đồ thị là không âm).

Ma trận kề của đồ thị có n đỉnh là ma trận vuông G có số hàng số cột là n. G[i][j] là độ dài đường đi từ đỉnh i tới đỉnh j. Nếu xét đồ thị vô hướng thì G[i][j] = G[j][i]. Độ dài từ một đỉnh tới chính nó luôn là 0 (G[i][i] = 0). Nếu giữa 2 cạnh i và j của đồ thị không tồn tại đường đi thì G[i][j] = vô cùng (∞). Tuy nhiên khi biểu diễn trong máy tính thì giá trị ∞ được đặt là 1 hằng số rất lớn hoặc là tổng các giá trị trong ma trận (tổng độ dài các cạnh).

1. Thuật toán Dijkstra

Về thuật toán Dijkstra có 2 loại là tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới 1 đỉnh đích và tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới các đỉnh còn lại của đồ thị, và ở đây mình sẽ nói về loại thứ 1. (loại thứ hai bạn có thể tìm trên mạng hoặc chỉ cần thay đổi dòng while (s[b] == 0) (dòng 43 của code 1 & dòng 76 của code 2) thành vòng for duyệt từ 0 đến n-1 là sẽ tìm được tất cả các đỉnh).

– Dùng 1 mảng Len[] – Len[i] là khoảng cách ngắn nhất từ đỉnh a tới đỉnh i.

– Dùng 1 mảng S đánh dấu các đỉnh i đặc biệt (các đỉnh i mà thời điểm hiện tại thì đường đi từ a tới i là ngắn nhất).

– Dùng mảng P[] đánh dấu đường đi. P[j] = i nếu i là đỉnh đi trước j trong đường đi ngắn nhất.

– Đặt lại giá trị vô cùng cho các cặp đỉnh không có đường đi.

– Khởi tạo tất cả các đường đi từ a đên các đỉnh khác bằng vô cùng.

– Khởi tạo đường đi từ a đến chính a = 0.

– Duyệt hết các đỉnh V của đồ thị

+ Tìm đỉnh i chưa nằm trong S mà đường đi từ a tới i là ngắn nhất để đưa vào S. Nếu không tìm được đỉnh nào nghĩa là đã duyệt hết các đỉnh có thể đi mà vẫn chưa thấy đỉnh đích => không thể đi được.

+ Nếu tìm được đỉnh i thì duyệt tất cả các đỉnh j chưa nằm trong S. Nếu Len[i] + G[i][j] < Len[j] (trong đó G[i][j] là khoảng cách từ đỉnh i tới đỉnh j) thì gán Len[j] = Len[i] + G[i][j]; và đánh dấu đường đi P[j] = i.

Lưu ý: Do trong C, mảng bắt đầu từ 0. Do vậy các đỉnh khi tính toán thì sẽ tính từ đỉnh 0 đến đỉnh n-1. Tuy nhiên khi hiển thị ra thì vẫn phải là từ đỉnh 1 đến n và trong file input.inp thì đỉnh đầu và đỉnh cuối cũng sẽ được tính từ 1 đến n. Do đó trong code trước khi tính toán ta cần giảm đỉnh đầu và đỉnh cuối đi 1 đơn vị. Sau khi tính toán xong thì khi xuất kết quả lại cần tăng các đỉnh trong đường đi tìm được lên 1 đơn vị để hiển thị đúng (VD ta muốn tính đường đi từ đỉnh 4 đến đỉnh 8, thì đỉnh 4 tương ứng với vị trí thứ 3 trong mảng, đỉnh 8 ứng với vị trí thứ 7 nên ta cần giảm 4 xuống 3, 8 xuống 7 để tính toán. Khi tìm được đường đi, giả sử là 3 -> 5 -> 4 -> 7 thì phải in ra là 4 -> 6 -> 5 -> 8).

Chúng ta sẽ đi thực hành với đồ thị sau theo 2 code là làm ngay trong main và thực hiện theo các hàm:

thuật toán tìm đường đi ngắn nhất

file input.inp: hàng đầu tiên thể hiện có 8 điểm, đi từ điểm 4 đến điểm 8. ma trận 8×8 ở dưới là ma trận kề của đồ thị.

8 4 8
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

* Code ngay trong main
Code này đã được sửa và khắc phục một số lỗi từ code ngày trước (hoặc link dự phòng).

#include <stdio.h>
#include <stdlib.h>
#define INP "input.inp"
#define OUT "output.out"
 
int main() {
    FILE *fi = fopen(INP, "r");
    FILE *fo = fopen(OUT, "w");
    int n, a, b, i, sum = 0;
 
    // nhap du lieu tu file input
    fscanf(fi, "%d%d%d", &n, &a, &b);
    int G[n][n];
    int S[n], Len[n], P[n];
 
    // nhap ma tran va tinh gia tri vo cung (sum)
    for (i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            fscanf(fi, "%d", &G[i][j]);
            sum += G[i][j];
        }
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;                   // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;                       // danh sach cac diem da xet
        P[i] = a;                       // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;                         // dat do dai tu a -> a la 0
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            break;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j]) {
                i = j;
            }
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
 
    printf("done dijkstra\n");
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    printf("start find path\n");
 
    if (Len[b] > 0 && Len[b] < sum) {
        fprintf(fo, "Length of %d to %d is %d\n", a + 1, b + 1, Len[b]);
 
        // truy vet
        while (i != a) {
            fprintf(fo, "%d <-- ", i + 1);
            i = P[i];
        }
        fprintf(fo, "%d", a + 1);
    } else {
        fprintf(fo, "khong co duong di tu %d den %d\n", a + 1, b + 1);
    }
 
    printf("done find path\n");
 
    fclose(fi);
    fclose(fo);
 
    printf("done - open file output to see result\n");
    return 0;
}

link dự phòng

* Code theo từng hàm
Trong code theo hàm có hàm:
– readData thực hiện đọc thông tin từ file input.
– dijkstra thực hiện thuật toán
– back thực hiện trả về chuỗi là đường đi tìm được
– outResult thực hiện in ra file output kết quả

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
 
#define INP "input.inp"
#define OUT "output.out"
 
// read data in file input
int readData(int ***G, int *n, int *a, int *b) {
    FILE *fi = fopen(INP, "r");
    if (fi == NULL) {
        printf("file input not found!\n");
        return 0;
    }
    printf("start read file\n");
 
    fscanf(fi, "%d %d %d", n, a, b);
 
    *G = (int **) malloc((*n) * sizeof(int));
    for (int i = 0; i < *n; i++) {
        (*G)[i] = (int *) malloc((*n) * sizeof(int));
        for (int j = 0; j < *n; j++) {
            int x;
            fscanf(fi, "%d", &x);
            (*G)[i][j] = x;
        }
    }
 
    fclose(fi);
    printf("done read file\n");
    return 1;
}
 
// thuat toan dijkstra
int dijkstra(int **G, int n, int a, int b, int P[]) {
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start dijkstra\n");
 
    int* Len = (int *) malloc(n * sizeof(int));
    int* S = (int *) malloc(n * sizeof(int));
 
    int sum = 0;            // gia tri vo cung
 
    // tinh gia tri vo cung (sum)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += G[i][j];
        }
    }
 
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;       // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;           // danh sach cac diem da xet
        P[i] = a;           // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;             // dat do dai tu a -> a la 0
 
    int i;
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            return 0;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j])
                i = j;
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
    printf("done dijkstra\n");
    return Len[b];
}
 
//  truy vet duong di
void back(int a, int b, int *P, int n, char *path) {
 
    //char *path = (char *) malloc((n * 10) * sizeof(char));
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start find path\n");
 
    int i = b;
    int point[n];   // danh sach cac dinh cua duong di
    int count = 0;
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    point[count++] = i + 1;
    while (i != a) {
        i = P[i];
        point[count++] = i + 1;
    }
 
    strcpy(path, "");
    char temp[10];
    for (i = count - 1; i >= 0; i--) {
        sprintf(temp, "%d", point[i]);
        strcat(path, temp);
 
        if (i > 0) {
            sprintf(temp, " --> ");
            strcat(path, temp);
        }
    }
 
    printf("done find path\n");
}
 
void outResult(int len, char* path) {
    FILE *fo = fopen(OUT, "w");
 
    if (len > 0) {
        fprintf(fo, "\nLength of %c to %c is %d\n", path[0],
                path[strlen(path) - 1], len);
    }
 
    fprintf(fo, "path: %s\n", path);
 
    fclose(fo);
}
 
int main() {
    int **G, n, a, b, len;
 
    if (readData(&G, &n, &a, &b) == 0) {
        return 0;
    }
 
    char *path = (char *) malloc((10 * n) * sizeof(char));
    int P[n];
 
    len = dijkstra(G, n, a, b, P);
 
    if (len > 0) {
        back(a, b, P, n, path);
        outResult(len, path);
    } else {
        char *path = (char *) malloc((n * 10) * sizeof(char));
        sprintf(path, "khong co duong di tu %d den %d\n", a, b);
        outResult(len, path);
    }
 
    printf("done - open file output to see result\n");
    return 0;
}

link dự phòng

Nhìn code có vẻ hơi dài nhưng khi đọc hiểu rồi thì chả dài tẹo nào @@ =)).

2. Thuật toán Floyd

Thuật toán này cho phép chúng ta tìm đường đi ngắn nhất giữa mọi cặp đỉnh.

Nếu đỉnh k nằm trên đường đi ngắn nhất từ đỉnh i tới đỉnh j thì đoạn đường từ i tới k và từ k tới j phải là đường đi ngắn nhất từ i tới k và từ k tới j tương ứng. Do đó ta sử dụng ma trận A để lưu độ dài đường đi ngắn nhất giữa mọi cặp đỉnh.
– Ban đầu ta đặt A[i,j] = C[i,j], tức là ban đầu A chứa độ dài đường đi trực tiếp (không đi qua đỉnh nào cả).
– Sau đó thực hiện n lần lặp, sau lần lặp thứ k, ma trận A sẽ chứa độ dài đường đi ngắn nhất giữa mọi cặp đỉnh chỉ đi qua các đỉnh thuộc tập {1,2,..,k}. Như vậy, sau n lần lặp ta nhận được ma trận A chứa độ dài các đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.

– Ký hiệu Ak là ma trận A sau lần lặp thứ k, tức là Ak[i,j] là độ dài đường đi ngắn nhất từ i đến j chỉ đi qua các đỉnh thuộc {1, 2,.., k}. Ak[i,j] được tính theo công thức như sau:    Ak[i,j] = min {Ak -1[i,j], Ak-1[i,k] + Ak-1[k,j]}.

– Trong quá trình lặp ta phải lưu lại vết đường đi, tức là đường đi ngắn nhất đi qua các đỉnh nào. Khi đó ta sử dụng mảng phụ P[nxn], trong đó P[i,j] lưu đỉnh k nếu đường đi ngắn nhất từ i đến j đi qua đỉnh k.  Ban đầu P[i,j]=0 với mọi i,j, vì lúc đó đường đi ngắn nhất là đường đi trực tiếp, không đi qua đỉnh nào cả.

Code thuật toán:

void Floyd (int a, int b)
{
    int max = tongthiethai();
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        {
            if (G[i][j])
                A[i][j] = G[i][j];
            else A[i][j] = max;
            P[i][j] = -1;
        }

    for (int k=0; k<n; k++)   // lap n lan
    {
        for (int i=0; i<n; i++)   // thay doi do dai duong di cua cac dinh
            for (int j=0; j<n; j++)
                if (A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = k ;
                }
    }
}

Cách xây dựng chương trình hoàn chỉnh hoàn toàn giống với thuật toán Dijkstra.

Code nâng cao


Đây là code cho phép chọn 1 trong 2 thuật toán trên và xuất ra file đúng theo quá trình làm như các kết quả trong hình bên dưới hoặc link dự phòng

file input.inp:

8
A B C D E F G H
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

Menu console
Đường đi ngắn nhất

Output Dijkstra
Dijkstra

Output Floyd
Floyd