Thuật toán tốt nhất để tìm localbridge (k) trong Biểu đồ là gì? Một cây cầu địa phương của độ k là một cạnh mà loại bỏ sẽ mở rộng khoảng cách ngắn nhất giữa hai điểm cuối của nó đến ít nhất k.LocalBridge độ k trong Biểu đồ
Wikipedia: http://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge
Chạy một thuật toán tất cả-ngắn-path-chi phí, giống như thuật toán Floyd-Warshall, nhưng mà bạn sử dụng các bộ (d1,d2) cho khoảng cách, thay vì những con số thực điển hình d:
d1 là chiều dài của con đường ngắn nhấtd2 là chiều dài của thứ hai Đường dẫn ngắn nhấtSửa đổi này đối với thuật toán Floyd-Warshall phải đơn giản.
Khi bạn làm xong chạy thuật toán tất cả-ngắn-path-chi phí, localbridge(k) cạnh là những cạnh e = {u, v} như vậy mà khoảng cách giữa (1,d2)u và v đáp ứng d2 >= k.
[Thuật toán Floyd-Warshall] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) có đủ tốt không? – anatolyg
Bạn có muốn tìm tất cả các cây cầu địa phương trong biểu đồ không? Có lẽ bạn đã có một (hoặc hai) nút cụ thể trong tâm trí. – phs