Tối ưu hóa Floyd-Warshall cho ma trận kề kề đối xứng

Question

Có tối ưu hóa làm giảm yếu tố không đổi của thời gian chạy Floyd-Warshall, nếu bạn được đảm bảo có ma trận kề kề đối xứng?

Answer 1

Sau khi một số nghĩ rằng tôi đến với:

for (int k = 0; k < N; ++k) 
    for (int i = 0; i < N; ++i) 
     for (int j = 0; j <= i; ++j) 
      dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 

Bây giờ tất nhiên cả hai chúng tôi cần phải chứng minh đó là chính xác và nhanh hơn.

Sự chính xác khó chứng minh hơn vì nó dựa trên bằng chứng về Floyd-Warshall, điều này không tầm thường. Một bằng chứng khá tốt được đưa ra ở đây: Floyd-Warshall proof

Ma trận đầu vào là symmetric. Bây giờ phần còn lại của bằng chứng sử dụng bằng chứng sửa đổi của Floyd-Warshall để cho thấy thứ tự tính toán trong 2 vòng trong không quan trọng và biểu đồ giữ nguyên đối xứng sau mỗi bước. Nếu chúng tôi cho thấy cả hai điều kiện này đều đúng thì cả hai thuật toán đều làm như vậy.

Hãy xác định dist[i][j][k] như khoảng cách i-j sử dụng chỉ sử dụng đỉnh từ tập {0, ..., k} như đỉnh trung gian trên con đường i-j.

dist[i][j][k-1] được định nghĩa là trọng số của cạnh từ i đến j. Nếu không có cạnh ở giữa trọng lượng này được lấy là vô cùng.

Bây giờ sử dụng cùng một logic được sử dụng trong các giấy tờ chứng minh liên kết ở trên:

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]) 

Bây giờ trong tính toán của dist[i][k][k] (và tương tự cho dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1]) 

Bây giờ kể từ dist[k][k][k-1] không thể phủ định (hoặc chúng tôi có một số negative loop trong biểu đồ), điều này có nghĩa là dist[i][k][k] = dist[i][k][k-1]. Vì nếu dist[k][k][k-1] = 0 thì cả hai tham số đều giống nhau, nếu không tham số đầu tiên của min() sẽ được chọn.

Vì vậy, bây giờ, bởi vì dist[i][k][k] = dist[i][k][k-1], khi tính dist[i][j][k] nó không quan trọng nếu dist[i][k] hoặc dist[k][j] đã cho phép k trong đường đi của họ. Vì dist[i][j][k-1] chỉ được sử dụng để tính toán dist[i][j][k], dist[i][j] sẽ ở lại dist[i][j][k-1] trong ma trận cho đến khi dist[i][j][k] được tính toán. Nếu i hoặc j bằng k thì trường hợp trên sẽ được áp dụng.

Do đó, thứ tự các phép tính không quan trọng.

Bây giờ, chúng tôi cần hiển thị rằng dist[i][j] = dist[j][i] sau tất cả các bước của thuật toán.

Chúng tôi bắt đầu với lưới đối xứng như vậy dist[a][b] = dist[b][a], cho tất cả a và b.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 
      = min(dist[j][i], dist[k][i] + dist[j][k]) 
      = min(dist[j][i], dist[j][k] + dist[k][i]) 
      = dist[j][i] 

Do đó, nhiệm vụ của chúng tôi là đúng và sẽ duy trì bất biến là dist[a][b] = dist[b][a]. Do đó, dist[i][j] = dist[j][i] sau tất cả các bước của thuật toán

Do đó cả hai thuật toán đều mang lại kết quả, kết quả chính xác, giống nhau.

Tốc độ dễ chứng minh hơn. Vòng lặp bên trong được gọi chỉ hơn một nửa số lần nó thường được gọi, vì vậy chức năng này nhanh gấp hai lần. Chỉ cần thực hiện chậm hơn một chút bởi vì bạn vẫn chỉ định cùng một số lần, nhưng điều này không quan trọng là min() là những gì chiếm phần lớn thời gian của bạn.

Nếu bạn thấy bất kỳ điều gì sai trái với bằng chứng của tôi, tuy nhiên kỹ thuật, vui lòng chỉ ra và tôi sẽ cố gắng khắc phục.

EDIT:

Bạn vừa có thể tăng tốc và tiết kiệm một nửa bộ nhớ bằng cách thay đổi vòng lặp như vậy:

for (int k = 0; k < N; ++k) { 
    for (int i = 0; i < k; ++i) 
     for (int j = 0; j <= i; ++j) 
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]); 
    for (int i = k; i < N; ++i) { 
     for (int j = 0; j < k; ++j) 
      dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]); 
     for (int j = k; j <= i; ++j) 
      dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]); 
    } 
} 

này chỉ tách lên phía trên cho các vòng của thuật toán tối ưu hóa, vì vậy nó vẫn chính xác và nó có thể sẽ có cùng tốc độ, nhưng sử dụng một nửa bộ nhớ.

Nhờ Chris Elion cho ý tưởng này.

Answer 2

(Sử dụng ký hiệu trong mã giả trong bài viết trên Wikipedia) Tôi tin (nhưng chưa thử nghiệm) rằng nếu ma trận edgeCost đối xứng, thì ma trận đường dẫn cũng sẽ đối xứng sau mỗi lần lặp. Vì vậy, bạn chỉ cần cập nhật một nửa số mục trong mỗi lần lặp.

Ở mức thấp hơn, bạn chỉ cần lưu trữ một nửa ma trận (vì d (i, j) = d (j, i)), vì vậy bạn có thể giảm lượng bộ nhớ được sử dụng, và hy vọng giảm số bộ nhớ cache bị bỏ lỡ vì bạn sẽ truy cập cùng một dữ liệu nhiều lần.