Hỏi về đồ thị và phép duyệt đồ thị

[dukksoocee (catsoougly412)]

Mọi người cho em hỏi về về bài này với:

Cho đồ thị và các đỉnh liên kết với nhau. Tìm đường đi từ S đến T sao cho trọng số nhỏ nhất trong các cạnh là lớn nhất so với các đường còn lại

VD:
4 S = 1, T =3
3 số i, j, k lần lượt là 2 đỉnh liên kết với nhau và k là trọng số
1 2 2
2 4 3
1 4 1
4 3 2

OUTPUT:
2
đường đi:
1 2 4 3

Ý tưởng của em: Dùng BFS hoặc DFS duyêt các đường đi có thể từ S tới T rồi lưu lại giá trị nhỏ nhất trên từng đường đi sau đó lấy max trong các min đó
Nhưng mà em nghĩ nếu làm như vậy có khả năng sẽ bị “bùng nổ tổ hợp” do quá nhiều đường đi, Em nghĩ có thể sử dụng tìm nhị phân ở đây nhưng cũng không chắc lắm nữa … EM đang bí mong mn giúp đỡ
(Em mới học đồ thị nên hơi luống cuống mong mn thông cảm)

[library (La biblioteca)]

@dukksoocee

Ý tưởng của em: Dùng BFS hoặc DFS duyêt các đường đi có thể từ S tới T rồi lưu lại giá trị nhỏ nhất trên từng đường đi sau đó lấy max trong các min đó

Cậu nên cài đặt Thuật toán Dijkstra để làm việc này

[Stanley00 (Stanley)]

Cách giải bần sau 30 giây suy nghĩ của /me:

1. Gán r = 0
2. Tìm đường đi bất kỳ P từ S đến T
3. Gán r = max(r, min(các cạnh trong P))
4. Xóa cạnh ngắn nhất trong P khỏi đồ thị
5. Lặp lại bước 2, 3, 4, 5 cho đến khi không tìm được P
6. Trả về r