Câu hỏi:
13/07/2024 49Tì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.
Trong cuộc sống chúng ta gặp rất nhiều bài toán liên quan đến tìm đường đi, dưới đây là một ví dụ cụ thể.
Có n sân bay được đánh số từ 0 đến n - 1, có m tuyến bay giữa các sân bay, tuyến thứ k sẽ bay từ sân bay i, sang sân bay j .Em hãy tìm cách di chuyển từ sân bay a tới sân bay b với số tuyến bay là ít nhất.
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 160k).
Quảng cáo
Trả lời:
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.
Trong cuộc sống chúng ta gặp rất nhiều bài toán liên quan đến tìm đường đi, dưới đây là một ví dụ cụ thể.
Có n sân bay được đánh số từ 0 đến n - 1, có m tuyến bay giữa các sân bay, tuyến thứ k sẽ bay từ sân bay i, sang sân bay j. cách di chuyển từ sân bay a tới sân bay b với số tuyến bay là ít nhất bằng cách biểu diễn đồ thị như sau:
a) 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).
b) 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.
c) 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) Chương trình Python:
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))
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Kiểm tra tính liên thông của đơn đồ thị có hướng
Trong đơn đồ thị có hướng, người ta thường quan tâm đến tính liên thông mạnh của đồ thị. Một đồ thị có hướng được gọi là liên thông mạnh nếu từ một đỉnh bất kì của đồ thị có thể đến được tất cả các đỉnh còn lại.
Các bài toán liên quan đến tính liên thông của đơn đồ thị có hướng cũng có nhiều ứng dụng như tính liên thông của đơn đồ thị vô hướng.
Câu 2:
Kiểm tra tính liên thông của đơn đồ thị vô hướng
Một đơn đồ thị vô hướng được gọi là liên thông nếu hai đinh bất kì của đồ thị đều có đường đi tới nhau.
Bài toán kiểm tra tính liên thông của đơn đồ thị vô hướng xuất hiện nhiều trong nghiên cứu lí thuyết cũng như ứng dụng trong cuộc sống, sau đây là một ví dụ cụ thể:
Có địa điểm được đánh số từ 0 đến n - 1, có m tuyến xe buýt hai chiều giữa các địa điểm, tuyển thứ k sẽ di chuyển giữa hai địa điểm ik, và jk, Em hãy kiểm tra xem từ một địa điểm bất kì có thể tới được các địa điểm còn lại bằng cách chỉ sử dụng m tuyển xe buýt hay không.
về câu hỏi!