Trọng số âm trong đồ thị có ý nghĩa gì?

[sike]

cho em hỏi trong thuật toán dijkstra thì yêu cầu các trọng số phải không âm , còn trong Ford Bellman lại cho phép trọng số âm , nhưng nếu 1 cung mà chứa trọng số âm thì ý nghĩa của cung đó là gì ?? không lẻ chi phí đi từ đỉnh này đến đỉnh kia là âm ??, không lẽ quảng đường từ nhà đến trường có thể âm được sao ?? về giải thuật với lý thuyết trên giấy thì em đã đọc và làm được nhưng nếu áp dụng vào thực tế nó sẽ ra sao khi 1 cung có trọng số âm ?

[tntxtnt]

trọng số có thể hiểu là đồ ăn hay xăng dầu chẳng hạn, ko nhất thiết phải là khoảng cách từ A tới B. Ví dụ đi từ A tới B khoảng cách là 10km, đi tốn 1 lít xăng, nhưng lại được thưởng 1 trái chuối, đi từ A tới C khoảng cách 5km nhưng có cây xăng giữa đường nên được cộng thêm 4 lít xăng, v.v… nên đó là trọng số âm :V

[noz1995 (Trần Hoàn)]

Không phải giải thuật chỉ dùng với khoảng cách, nó còn dùng với bất kỳ đại lượng nào trong bài toán chi phí. Và có những giai đoạn có thể sinh lời, tuy nhiên sẽ đi kèm với các điều kiện khác, chẳng hạn như giới hạn số lần lặp lại giai đoạn đó.