Thứ Hai, 25 tháng 11, 2013

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

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 đếnb.
Như tiêu đề bài viết, chúng ta sẽ tìm hiểu 2 thuật toán để giải quyết (chú ý ta xét trọng số của đồ thị là không âm):


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ứ 2. (loại thứ nhất bạn có thể tìm trên mạng).
Thuật toán:
- 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.
- Khởi tạo tất cả các đường đi 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.
+ 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.
Code thuật toán:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>
#define INP "input.inp"
#define OUT "output.out"
int main()
{
    FILE *f = fopen(INP, "r");
    int n, a, b, i, sum = 0;
    fscanf(f,"%d%d%d", &n, &a, &b);
    int G[n][n];
    int s[n], Len[n], P[n];
 
    for (i = 0; i<n; i++)        // nhap ma tran
        for (int j=0; j<n; j++)
        {
            fscanf(f, "%d", &G[i][j]);
            sum += G[i][j];
        }
    for (int i=0; i<n; i++)      // dat vo cung bang tong gia tri ma tran
    {
        for (int j=0; j<n; j++)
        {
            printf("%3d", G[i][j]);
            if (G[i][j] == 0) G[i][j] = sum;
        }
        printf("\n");
    }
 
    for (int i=0; i<n; i++)
    {
        Len[i] = sum;       // do dai den diem i
        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
 
    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;
        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++)  // dubet 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("\nLength of %d to %d is %d\n",a, b, Len[b]);
 
    // truy vet
    i = b;
    while (i != a)
    {
        printf("%d <-- ", i);
        i = P[i];
    }
    printf("%d", a);
 
    return 0;
}
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 ;
                }
    }
}
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