Floyd-Warshall thuật toán logic - Stuck

Question

Tôi cố gắng để sử dụng logic này để hiểu những gì đang xảy ra với adjacency matrix, nhưng tôi massivley bối rối nơi nó nói về interspacing cho abcd .....

Có thể bất cứ ai giải thích những gì đang xảy ra ở đây?

Cảm ơn bạn (gắn thẻ như java là ngôn ngữ của nó này đã được chứng minh cho chúng ta trong, vì vậy nếu có ai gửi bất kỳ ví dụ mã họ có thể thấy đó là trong ngôn ngữ đó)

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

Đây là mã:

for (k = 0; k < n; ++k) { 
    for (i = 0; i < n; ++i) 
     for (j = 0; j < n; ++j) 
      /* If i and j are different nodes and if 
       the paths between i and k and between 
       k and j exist, do */ 
      if ((dist[i][k] * dist[k][j] != 0) && (i != j)) 
       /* See if you can't get a shorter path 
        between i and j by interspacing 
        k somewhere along the current 
        path */ 
       if ((dist[i][k] + dist[k][j] < dist[i][j]) || 
         (dist[i][j] == 0)) 
        dist[i][j] = dist[i][k] + dist[k][j]; 

Answer 1

các thuật toán Floyd-Warshall nào sau đây:

Nó nhìn vào e nút ach (k) và sau đó xem trong mỗi k -iteriter cho mỗi i, j, nếu nó có thể có một con đường ngắn hơn bằng cách đi đầu tiên từ i đến k và sau đó từ k đến j.

Vì vậy, nó trông giống:

"My con đường hiện ngắn nhất i-j là chiều dài L0, con đường hiện ngắn nhất của tôi i-k là chiều dài L1, con đường hiện ngắn nhất của tôi k-j là chiều dài L2.

gì nếu tôi kết hợp các đường dẫn hiện ngắn nhất i to k và k to j đến một con đường mới? là con đường mới này i to k to j ngắn hơn so với tôi con đường ngắn nhất hiện nay i to j? Nếu vậy, nó tích lũy độ dài L1 và L2 để tính độ dài của đường đi ngắn mới."

Điều đó có nghĩa, k là một điểm dừng chân tiềm năng cho một cách i-j.

Answer 2

Floyd- Warshall là một vấn đề dynamic programming

nó gần chuẩn (và dễ dàng hơn) để viết nó trong phiên bản 2 chiều:.

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

nhưng có lẽ nó giúp bạn hình dung nó với các phiên bản 3 chiều, vì vậy bạn có thể xem tất cả các quốc gia một cách rõ ràng hơn:

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

một lời giải thích một chút sâu sắc hơn về các bang được tìm thấy ở Algorithmist.