ìm đường đi ngắn nhất trên đơn đồ thị có hướng Một dãy đỉnh a = i0, i1,..., is = b (a ≠ b) được gọi là đường đi từ đinh a tới đỉnh b nếu hai đỉnh liên tiếp trên đường đi có cạnh nối...

Gợi ý cách thực hiện thuật toán:

1. Biểu diễn đồ thị:

   • Sử dụng danh sách kề (adjacency list) để biểu diễn đồ thị có hướng. Mỗi đỉnh (sân bay) sẽ có một danh sách các đỉnh mà nó có cạnh nối tới (các sân bay có tuyến bay trực tiếp tới).

2. Thuật toán BFS:

   • BFS là thuật toán tìm kiếm theo chiều rộng, rất hiệu quả trong việc tìm đường đi ngắn nhất trên đồ thị không trọng số.

   • Khởi tạo một hàng đợi (queue) và đưa đỉnh bắt đầu aaa vào hàng đợi.

   • Sử dụng một mảng để theo dõi các đỉnh đã được thăm và mảng này cũng lưu khoảng cách từ đỉnh aaa tới các đỉnh khác.

   • Trong khi hàng đợi không rỗng, lấy đỉnh đầu hàng đợi ra và duyệt qua tất cả các đỉnh kề của nó. Nếu đỉnh kề chưa được thăm, đánh dấu nó đã được thăm và thêm nó vào hàng đợi.

3. Truy vết đường đi:

   • Để truy vết đường đi từ bbb về aaa, chúng ta có thể sử dụng một mảng cha (parent array) để lưu đỉnh trước đó của mỗi đỉnh trong quá trình BFS.

   • Khi tìm thấy đỉnh bbb, chúng ta có thể truy ngược lại từ bbb về aaa để xác định đường đi.

Dưới đây là mã Python chi tiết để thực hiện điều này:

python

Sao chép mã

from collections import deque

def shortest_path(n, edges, a, b):

   # Bước 1: Xây dựng đồ thị dưới dạng danh sách kề

   graph = [[] for _ in range(n)]

   for edge in edges:

        i, j = edge

        graph[i].append(j)

   # Bước 2: BFS để tìm đường đi ngắn nhất

   queue = deque([a])

   visited = [False] * n

   distance = [-1] * n  # Khoảng cách từ a tới các đỉnh

   parent = [-1] * n  # Để truy vết đường đi

   visited[a] = True

   distance[a] = 0

   while queue:

        current = queue.popleft()

        for neighbor in graph[current]:

            if not visited[neighbor]:

                visited[neighbor] = True

                distance[neighbor] = distance[current] + 1

                parent[neighbor] = current

                queue.append(neighbor)

                if neighbor == b:

                    # Nếu đã tới đích, dừng BFS

                    queue.clear()

                    break

   # Bước 3: Truy vết đường đi từ b về a

   path = []

   if visited[b]:

        current = b

        while current != -1:

            path.append(current)

            current = parent[current]

        path.reverse()

   return path if path and path[0] == a else []

# Ví dụ sử dụng:

n = 5  # Số sân bay

edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]  # Các tuyến bay

a = 0  # Sân bay bắt đầu

b = 4  # Sân bay đích

print(shortest_path(n, edges, a, b))