Câu hỏi:

13/07/2024 76

Tìm đường đi ngắn nhất trên đơn đồ thị có hướng

Một dãy đỉnh a = i0, i1,..., i= 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: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).

Tổng ôn toán Tổng ôn sử Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Một dãy đỉnh a = i0, i1,..., i= 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))

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.

Xem đáp án » 13/07/2024 613

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.

Xem đáp án » 13/07/2024 138

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

Vietjack official store