Algorithm: Floyd–Warshall và bài toán đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị

Thuật toán Floyd-Warshall hay còn gọi là Floyd, Roy-Floyd là thuật toán tìm đường đi ngẵn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số được công bố năm 1962 bởi Robert Floyd . Trong bài này tôi sẽ giới thiệu cách cài đặt thuật toán này trong chương trình Y2 Visual Graph đã giới thiệu trước đây.

Thuật toán Floyd cài đặt khá đơn giản, dựa trên ý tưởng: Nếu có đường đi từ i tới k và từ k tới j nhỏ hơn đường đi hiện tại từ i tới j thì ta sẽ cập nhật đường đi từ i tới j thành đường đi từ i tới k cộng với từ k tới j. Ta gọi k là đỉnh trung gian của i và j. Như vậy sau khi thực hiện thuật toán, sẽ có một số cạnh “ảo” được sinh ra, tức là các cạnh không nối trực tiếp giữa hai đỉnh.

for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
path[i,j] := min (path[i,j] , path[i,k] + path[k,j] );

Như vậy mặc dù có độ phức tạp lên tới O(n^3) nhưng ta chỉ cần thực hiện 1 lần là có thể tìm đường đi ngắn nhất giữa hai đỉnh bất kì.

Tham khảo thêm tại:

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Cài đặt bằng C#

Trong bài toán này tôi sử dụng ma trận kề với giá trị data[i,j] = -1 để biểu diễn không có đường đi giữa hai đỉnh i và j. Sau đó tạo thêm một mảng 2 chiều FloydData để lưu kết quả sau quá trình thực hiện thuật toán Floyd.

public void Floyd()
{
    if (Data == null)
        return;
    int n = Data.GetLength(0);

    FloydData = new MatrixCell[n, n];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            FloydData[i, j] = new FloydCell(Data[i, j]);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (FloydData[j, i].Value > 0)
            {
                for (int k = 0; k < n; k++)
                {
                    if (FloydData[i, k].Value > 0)
                    {
                        if (FloydData[j, k].Value < 0 || FloydData[j, i].Value + FloydData[i, k].Value < FloydData[j, k].Value)
                        {
                            FloydData[j, k].Value = FloydData[j, i].Value + FloydData[i, k].Value;

                            FloydData[j, k].Previous = i;
                        }
                    }
                }
            }
        }
    }
}

FloydCell là một struct được định nghĩa để lưu trữ giá trị trọng số của cạnh và đỉnh trung gian:

struct FloydCell
{
    public int Previous;
    public int Value;

    public FloydCell(int value)
        : this(-1, value)
    { }
    public FloydCell(int previous, int value)
    {
        this.Previous = previous;
        this.Value = value;
    }
}

Lý do ta cần phải lưu lại đỉnh trung gian là để lấy được đường đi qua các đỉnh từ đỉnh bắt đầu đến kết thúc. Bạn sẽ thấy rõ hơn công dụng của giá trị này trong phần tiếp theo.

Lấy đường đi ngắn nhất giữa hai đỉnh

List<Point> _path = new List<Point>();
// […]
void GetPath(int x,int y)
{
    if(_matrix.FloydData[x,y].Value== -1)
        return;
    int i=_matrix.FloydData[x,y].Previous;
    if(i== -1)
    {
        _path.Add(new Point(x+1,y+1));
        return;
    }
    else
    {
        GetPath(x,i);
        _path.Add(new Point(_preNodeIndex+1,i+1));
        _preNodeIndex=i;
        GetPath(i,y);
    }
}

Phương thức GetPath() trên sẽ tạo ra đường đi giữa hai đỉnh x, y và lưu vào trong collection _path. Giá trị của FloydData[x,y].Previous sẽ trả về đỉnh trung gian giữa hai đỉnh x,y và nếu giá trị này bằng -1 tức là có một cạnh nối trực tiếp giữa hai đỉnh này. Ngược lại ta chia đường đi thành hai phần và thực hiện đệ quy để lấy đường đi của từng phần này.

Minh họa trong Y2 Visual Graph

https://yinyangit.wordpress.com

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s