Lập trình Python

Thuật toán Bellman-Ford

Posted on by Đỗ Thành
25
Th3
View: 60

Giới thiệu thuật toán Bellman-Ford

Thuật toán Bellman-Ford là một thuật toán quan trọng trong lý thuyết đồ thị và được sử dụng để tìm đường đi ngắn nhất từ một đỉnh bất kỳ đến tất cả các đỉnh khác trên đồ thị có hướng hoặc không có hướng, với trọng số âm được phép. Thuật toán này còn được sử dụng để tìm chu trình âm trong đồ thị có trọng số.

Thuật toán Bellman-Ford hoạt động bằng cách tạo ra một bảng đường đi ngắn nhất ban đầu với đỉnh xuất phát là 0, và tất cả các đỉnh khác là vô cực. Sau đó, thuật toán sử dụng phương pháp lặp để cập nhật bảng này, bằng cách lấy giá trị của mỗi đỉnh là khoảng cách ngắn nhất từ đỉnh xuất phát đến đỉnh đó.

Thuật toán Bellman-Ford có độ phức tạp O(|V|*|E|), trong đó |V| là số lượng đỉnh của đồ thị và |E| là số lượng cạnh. Với trường hợp đồ thị không có chu trình âm, thuật toán Bellman-Ford sẽ tìm ra đường đi ngắn nhất từ đỉnh xuất phát đến tất cả các đỉnh khác trong đồ thị. Tuy nhiên, nếu đồ thị có chu trình âm, thuật toán sẽ không thể tìm ra đường đi ngắn nhất và sẽ chỉ ra rằng đồ thị có chu trình âm.

Các bước thực hiện thuật toán Bellman-Ford

Các bước thực hiện thuật toán Bellman-Ford như sau:

  1. Khởi tạo bảng đường đi ngắn nhất:

    • Gán đỉnh xuất phát có giá trị bằng 0, và tất cả các đỉnh khác có giá trị là vô cực.

  2. Lặp lại việc cập nhật bảng đường đi ngắn nhất cho tất cả các đỉnh trên đồ thị, lặp lại |V| – 1 lần.

    • Duyệt qua tất cả các cạnh trên đồ thị và cập nhật giá trị đường đi ngắn nhất cho các đỉnh kết thúc của các cạnh đó.
    • Nếu giá trị đường đi từ đỉnh bắt đầu đến đỉnh kết thúc của cạnh đang xét nhỏ hơn giá trị đường đi hiện tại của đỉnh kết thúc, ta cập nhật giá trị đường đi của đỉnh kết thúc bằng giá trị đường đi mới này.

  3. Kiểm tra xem đồ thị có chu trình âm hay không:

    • Lặp lại việc duyệt qua tất cả các cạnh trên đồ thị và kiểm tra xem có cạnh nào khi được cộng với giá trị đường đi của đỉnh bắt đầu lớn hơn giá trị đường đi hiện tại của đỉnh kết thúc hay không. Nếu có, đồ thị có chu trình âm.

  4. Kết quả:

    • Kết quả cuối cùng là bảng đường đi ngắn nhất từ đỉnh xuất phát đến tất cả các đỉnh khác trên đồ thị.

Lưu ý: Trong trường hợp đồ thị không liên thông, ta cần phải áp dụng thuật toán Bellman-Ford cho từng thành phần liên thông của đồ thị.

Ví dụ về thuật toán Bellman-Ford

Giả sử chúng ta có đồ thị sau đây với 4 đỉnh và 5 cạnh:

    (1)--3-->(2)
     |       /|\
    4|      / | \
     |     /  |  \5
    \|/   /   |   \
    (3)<--1--(4)--->

Giả sử đỉnh xuất phát là đỉnh 1. Ta bắt đầu bằng cách khởi tạo bảng đường đi ngắn nhất như sau:

ĐỉnhĐường đi ngắn nhất
10
2∞
3∞
4∞

Lần lượt cập nhật bảng đường đi ngắn nhất cho tất cả các đỉnh trên đồ thị. Sau khi lặp lại |V| – 1 lần (tức là 3 lần ở đây), ta thu được bảng đường đi ngắn nhất như sau:

ĐỉnhĐường đi ngắn nhất
10
23
34
46

Ta thấy rằng đường đi ngắn nhất từ đỉnh 1 đến đỉnh 2 là 3, từ đỉnh 1 đến đỉnh 3 là 4, từ đỉnh 1 đến đỉnh 4 là 6.

Cài đặt thuật toán Bellman-Ford với Python

INF = float('inf')

def bellman_ford(graph, start):
    # Khởi tạo bảng đường đi ngắn nhất, tất cả các đỉnh ban đầu đều có khoảng cách vô cùng đến đỉnh bắt đầu.
    dist = {v: INF for v in graph}
    dist[start] = 0

    # Lặp lại |V| - 1 lần để cập nhật bảng đường đi ngắn nhất cho tất cả các đỉnh trên đồ thị.
    for _ in range(len(graph) - 1):
        # Lặp qua tất cả các cạnh trên đồ thị.
        for u in graph:
            for v, w in graph[u].items():
                if dist[u] != INF and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

    # Kiểm tra nếu còn đường đi ngắn hơn, tức là có chu trình âm trên đồ thị.
    for u in graph:
        for v, w in graph[u].items():
            if dist[u] != INF and dist[u] + w < dist[v]:
                return None

    return dist

Hàm bellman_ford nhận đầu vào là một đồ thị dưới dạng danh sách kề (graph) và đỉnh xuất phát (start). Đầu ra của hàm là một bảng đường đi ngắn nhất từ đỉnh xuất phát đến tất cả các đỉnh khác trong đồ thị. Nếu đồ thị có chu trình âm thì hàm sẽ trả về None.

Bạn có thể sử dụng đoạn mã này để thực hiện thuật toán Bellman-Ford trên các đồ thị của riêng mình. Ví dụ: Dưới đây là đoạn mã Python triển khai thuật toán Bellman-Ford trên đồ thị với trọng số cạnh là số nguyên.

from collections import defaultdict

def bellman_ford(graph, start):
    # Khởi tạo bảng đường đi ngắn nhất, tất cả các đỉnh ban đầu đều có khoảng cách vô cùng đến đỉnh bắt đầu.
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0

    # Lặp lại |V| - 1 lần để cập nhật bảng đường đi ngắn nhất cho tất cả các đỉnh trên đồ thị.
    for _ in range(len(graph) - 1):
        # Lặp qua tất cả các cạnh trên đồ thị.
        for u in graph:
            for v, w in graph[u].items():
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

    # Kiểm tra nếu còn đường đi ngắn hơn, tức là có chu trình âm trên đồ thị.
    for u in graph:
        for v, w in graph[u].items():
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                return None

    return dict(dist)

# Ví dụ về việc sử dụng thuật toán Bellman-Ford
graph = {
    'A': {'B': -1, 'C':  4},
    'B': {'C':  3, 'D':  2, 'E':  2},
    'C': {},
    'D': {'B':  1, 'C':  5},
    'E': {'D': -3}
}

start = 'A'
dist = bellman_ford(graph, start)
print(f'Bảng đường đi ngắn nhất: {dist}')

Trong ví dụ này, đầu vào của hàm bellman_ford là một đồ thị dưới dạng một dictionary có trọng số cạnh là số nguyên. Đầu ra là một dictionary có khoảng cách từ đỉnh xuất phát đến tất cả các đỉnh khác trong đồ thị. Nếu đồ thị có chu trình âm, hàm sẽ trả về None.

Đánh giá độ phức tạp của Thuật toán Bellman-Ford

Độ phức tạp của thuật toán Bellman-Ford là O(|V| * |E|), trong đó |V| là số lượng đỉnh của đồ thị và |E| là số lượng cạnh của đồ thị.

Trong thuật toán, chúng ta lặp qua mỗi cạnh của đồ thị tới |E| lần, và với mỗi cạnh, chúng ta thực hiện việc cập nhật bảng đường đi ngắn nhất. Việc cập nhật này tốn O(1) thời gian. Do đó, tổng thời gian thực hiện là O(|V| * |E|).

Độ phức tạp của thuật toán Bellman-Ford không hiệu quả bằng các thuật toán như Dijkstra và A* vì nó phải lặp lại cập nhật bảng đường đi ngắn nhất cho mỗi đỉnh trên đồ thị, dẫn đến độ phức tạp tăng lên đáng kể với số lượng đỉnh và cạnh của đồ thị. Tuy nhiên, điểm mạnh của thuật toán Bellman-Ford là nó có thể xử lý được đồ thị có trọng số âm và chu trình âm trên đồ thị.

12 thoughts on “Thuật toán Bellman-Ford”

  6. sklep internetowy says:

    Hi! Do you know if they make any plugins to help with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not
    seeing very good success. If you know of any please share.
    Many thanks! You can read similar article here: Sklep

    Trả lời
  7. e-commerce says:

    Hello there! Do you know if they make any plugins to help
    with Search Engine Optimization? I’m trying to get my blog to rank for some targeted
    keywords but I’m not seeing very good results. If you know of any
    please share. Many thanks! You can read similar article here:
    Najlepszy sklep

    Trả lời
  10. List of Backlinks says:

    Hello there! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to get my website to
    rank for some targeted keywords but I’m not seeing very good success.
    If you know of any please share. Appreciate it!
    You can read similar art here: Auto Approve List

    Trả lời
  11. Marcos says:

    Hey! Do you know if they make any plugins to assist with Search
    Engine Optimization? I’m trying to get my website to rank for some targeted keywords
    but I’m not seeing very good success. If you know of any please
    share. Appreciate it! I saw similar blog here: GSA List

    Trả lời

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *