14
Trong thuật toán đường đi ngắn nhất của Dijkstra và các thuật toán khác, để kiểm tra một cạnh để xem nó có cung cấp đường dẫn tốt hơn đến một nút hay không được gọi là thư giãn cạnh. Tại sao nó được gọi là thư giãn?Tại sao chúng ta gọi nó là "Thư giãn" một cạnh?
Bạn có thể làm rõ các cạnh trong hồ bơi có thể được xem như là những ràng buộc không? –
Hãy suy nghĩ về một đỉnh với rất nhiều cạnh đi vào nó. Khi bạn bắt đầu, bạn hnow giải pháp đã bao gồm teh trọng lượng từ cạnh đầu tiên, cạnh thứ hai, và như vậy. Trong thực tế, đối với các cạnh a, b, c, d và e, bạn bắt đầu nói "đường đi ngắn nhất phải bao gồm a, b, c, d, e". Sau đó, bạn loại bỏ e, và bây giờ bạn biết là phải bao gồm chỉ "a, b, c, d". Mỗi bước là một * thư giãn * bởi vì ở mỗi bước bạn loại bỏ một điều kiện giải pháp hiện tại áp đặt. –
Tôi đoán nó không phải là 'đi vào nó' nhưng 'để lại nó'? –