Bài toán tìm đường đi trong ma trận c++ năm 2024

Trong những bài toán đường đi ngắn nhất mà chúng ta cần thông tin về đường đi giữa nhiều cặp đỉnh, ta có xu hướng là sẽ tính toán đường đi ngắn nhất giữa mọi cặp đỉnh.

Thuật toán Floyd-Warshall là một thuật toán phù hợp để thực hiện tác vụ này.

Trước hết, ta cần phải nắm về khâu tổ chức dữ liệu: đường đi ngắn nhất giữa 2 đỉnh bất kỳ sẽ được lưu trong một mảng 2 chiều, ngầm định sẽ có giá trị là +INF nếu không có đường nối trực tiếp giữa chúng, hoặc nếu có đường nối thì giá trị ban đầu sẽ là trọng số của đường nối đó. Các tính toán sau này sẽ là so sánh giữa đường đi ngắn nhất hiện tại với một đường đi trung gian [giả sử, với 2 đỉnh A và B, ta so sánh đường đi ngắn nhất hiện thời giữa 2 đỉnh này với tổng độ dài đường đi ngắn nhất từ A và từ B tới 1 đỉnh C trung gian nào đó].

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O[V^2].

Ta xét đồ thị vô hướng sau:

Từ quy tắc trên, mảng 2D chứa đường đi ngắn nhất ban đầu sẽ được khởi tạo như sau:

Từ đây, quá trình thực hiện thuật toán Floyd-Warshall sẽ diễn ra như sau:

• Chọn lần lượt từng đỉnh của đồ thị làm đỉnh trung gian [ta quy ước là C].
  • Chọn một cặp 2 đỉnh phân biệt và không trùng với đỉnh trung gian [ta quy ước lần lượt là A và B].
    • Thực hiện so sánh như ở trên: đường đi ngắn nhất giữa A và B sẽ bằng giá trị nhỏ nhất của:
      • Giá trị đường đi ngắn nhất hiện thời giữa A và B.
      • Tổng của giá trị đường đi ngắn nhất hiện thời giữa A và C, và đường đi ngắn nhất hiện thời giữa B và C.

Ta sẽ phân tích tuần tự theo nền tảng ý tưởng này:

Đầu tiên, C = 1. Nhờ đỉnh 1 làm trung gian, ta thấy xuất hiện đường đi từ đỉnh 2 tới đỉnh 4 [độ dài 14], và từ đỉnh 2 tới đỉnh 5 [độ dài 6].

Đường đi trung gian qua đỉnh 1 để đi từ đỉnh 4 tới đỉnh 5 không tối ưu về chiều dài [9 + 1 > 2] nên ta không cập nhật lại đường đi ngắn nhất giữa 2 đỉnh 4 và 5.

Mảng 2D lúc này trở thành:

Tiếp theo, ta duyệt tới C = 2.

Đường đi từ 3 tới 1 [độ dài 7], từ 3 tới 5 [độ dài 8] được hình thành.

Đường đi từ 3 tới 4 không cập nhật độ dài [7 < 2 + 5 + 9].

Mảng 2D lúc này là:

Cứ tiếp tục lựa chọn C như vậy cho tới hết, ta sẽ thu được mảng 2D hoàn chỉnh:

Giả sử, qua mảng này, ta thấy đường đi ngắn nhất từ đỉnh 2 tới đỉnh 4 có độ dài 8. Dựa theo đồ thị thì nó là đoạn đường sau:

Quá trình cài đặt thuật toán Floyd-Warshall khá đơn giản, có thể chia làm 2 công đoạn:

1. Khởi tạo mảng 2D chứa đường đi ngắn nhất [ở code này thì đồ thị được biểu diễn ở dạng ma trận kề, và distance là tên mảng]:
2. Tính toán giá trị đường đi ngắn nhất:

Hoàn toàn dễ dàng nhận ra, thuật toán có độ phức tạp O[V^3]. Do đó, thuật toán chỉ nên áp dụng với những đồ thị có số đỉnh nhỏ [thường chỉ tới 100-200 đỉnh].

Bài toán tham khảo: CS Academy – Round 70 – Min Distances

Tóm tắt đề bài:

Cho 2 số N và M, và M bộ 3 số [a, b, c].

Hãy tạo ra một đồ thị đơn vô hướng, liên thông, có trọng số với N đỉnh, sao cho với mỗi bộ số [a, b, c] đề cập ở trên, đường đi ngắn nhất giữa đỉnh a và đỉnh b phải bằng c.

Mọi cạnh trên đồ thị được in ra có trọng số không quá 10^7.

Nếu không có đồ thị thỏa mãn, in ra -1.

Phương pháp:

Trường hợp duy nhất để không tìm thấy đồ thị thỏa mãn là các cạnh bị ràng buộc chồng chéo lên nhau – theo cách mà 2 cạnh ràng buộc trung gian có độ dài ngắn hơn một cạnh ràng buộc khác.

Ta nhận thấy, ta hoàn toàn có thể lập một đồ thị đầy đủ, với trọng số tất cả các cạnh bằng 10^7. Với mỗi bộ số [a, b, c], ta gán lại trọng số của cạnh [a, b] bằng c.

Như vậy, ít nhất nếu không tính các đường đi gián tiếp, đồ thị ta lập ra vẫn thỏa mãn ràng buộc của đề bài.

Tới đây, ta có thể sử dụng thuật toán Floyd để tìm đường đi ngắn nhất của tất cả các cặp đỉnh trên đồ thị.

Nếu không có bộ số [a, b, c] nào mà đường đi ngắn nhất từ a tới b khác c, thì đồ thị đó là thỏa mãn, và có thể in ra.

Ngược lại, in ra -1.

Lời giải [của neko_nyaa]: CS Academy – Submission 1372996

Lời giải [của D.Bách]: CS Academy – Submission 1370237

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.