Floyd-Warshall Algoritmo Logic - Bloccato

Question

Sto cercando di usare questa logica per capire cosa sta succedendo con la adjacency matrix, ma io sono massivley confuso in cui si dice circa interspacing per abcd .....

si poteva spiegare cosa sta succedendo qui?

Grazie (contrassegnati come java come il suo linguaggio questo è stato dimostrato a noi in, quindi se qualcuno ha postato qualche esempio di codice hanno potuto vedere che era in quella lingua)

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

Ecco il codice:

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

l'algoritmo di Floyd-Warshall esegue le seguenti operazioni:

Si guarda e ach node (k) e poi guarda ogni -iteration per ogni i, j, se può avere un percorso più breve andando prima da i a k e quindi da k a j.

in modo che appaia:

"Il mio percorso attualmente più breve i-j è di lunghezza L0, il mio percorso attualmente più breve i-k è di lunghezza L1, il mio percorso attualmente più breve k-j è di lunghezza L2.

e se combino i percorsi più brevi attualmente i to k e k to j ad un nuovo percorso? e 'questo nuovo percorso i to k to j più breve rispetto il mio momento più breve percorso i to j? In caso affermativo, si accumula le lunghezze L1 e L2 per calcolare la lunghezza del nuovo percorso più breve."

Ciò significa, k è un potenziale punto di sosta per una strada da i a j.

Answer 2

Floyd- Warshall è un problema dynamic programming

è quasi standard (e più facile) di scrivere nella versione a 2 dimensioni:.

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]) 

ma forse aiuta a Picture It con la versione 3-dimensionale, in modo da poter vedere tutti gli stati più esplicitamente:

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]) 

una spiegazione leggermente più profondo degli stati si trova al Algorithmist.