––––•(-• (Last † Kill) •-)•––––


    Trình bày thuật toán tìm đường đi ngắn nhất?

    Share

    Admin
    Admin

    Tổng số bài gửi : 58
    Join date : 05/05/2011
    Age : 26

    Trình bày thuật toán tìm đường đi ngắn nhất?

    Bài gửi  Admin on Sun Jun 05, 2011 9:05 pm

    Bài toán(1 điểm): Cho đồ thị G = (V, E) và hai đỉnh a, b. Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh a đến đỉnh b trong đồ thị G.
    ý nghĩa thực tế: Bài toán này giúp chúng ta chọn các hành trình tiết kiệm nhất
    (quãng đường, thời gian, chi phí ...) trong giao thông, lập lịch thi công các công trình một cách tối ưu, xử lý trong truyền tin ...Thuật toán duyệt đồ thị theo chiều rộng đã cho ta lời giải của bài toán này.
    Song ta có thêm thuật toán sau đây.
    Thuật toán 8.1(1 điểm):
    1. Lần lượt gán nhãn cho các đỉnh của đồ thị, mỗi đỉnh không quá một lần, như sau:
    - Đỉnh a được gán nhãn là số 0.
    - Những đỉnh kề với đỉnh a được gán số 1.
    - Những đỉnh kề với đỉnh đã được gán nhãn số 1, được gán số 2.
    ………………………………….
    - Tương tự, những đỉnh kề với đỉnh đã được gán số i được gán nhãn là số
    i+1.
    ………………………………….
    Thực hiện cho đến khi gán được nhãn cho đỉnh b hoặc không gán nhãn
    được nữa.
    2. Nếu đỉnh b được gán nhãn nào đó là k thì kết luận có đường đi ngắn nhất từ đỉnh a tới đỉnh b với độ dài k, ngược lại thì trả lời là không có.
    3. Khôi phục đường đi: Nếu ở bước 2. chỉ ra b được gán nhãn k nào đó thì ta đi ngược lại theo quy tắc sau đây: Nếu đỉnh y được gán nhãn j với j ≥ 1 thì sẽ có đỉnh x được gãn nhãn j-1 sao cho có cạnh đi từ x tới y. Đi ngược lại cho đến khi gặp đỉnh a, ta nhận được đường đi ngắn nhất cần tìm.

      Hôm nay: Thu Sep 21, 2017 4:52 am