[ Advanced algorithm] 2
Cho đồ thị vô hướng liên thông n đỉnh, các đỉnh được đánh số từ 1 tới n. Biết khoảng cách giữa 2 đỉnh có cạnh nối luôn là 1. Hãy viết hàm trả về khoảng cách của đường đi ngắn nhất từ đỉnh 1 tới tất cả các đỉnh.
Ví dụ
- Cho
edges = [[1, 2], [2, 3], [1, 3], [2, 4]], output sẽ có dạngshortestPath(edges) = [0, 1, 1, 2].
Giải thích:- Khoảng cách từ đỉnh
1tới chính nó luôn là0. - Do có cạnh nối trực tiếp từ đỉnh
1tới đỉnh2và3nên khoảng cách tới đỉnh2và3là1. - Từ đỉnh
1tới đỉnh4phải đi qua đỉnh2nên khoảng cách tới đỉnh4là2.
- Khoảng cách từ đỉnh
Đầu vào/Đầu ra
- [Thời gian chạy] 0.5s
- [Đầu vào] Matrix of integers edges
- [Đầu ra] Array of integers
Post Comment