फ्लोयड-Warshall एल्गोरिथ्म तर्क - Stuck

Question

मैं इस तर्क का उपयोग करने के समझने के लिए adjacency matrix साथ चल रहा है कोशिश कर रहा हूँ, लेकिन मैं massivley उलझन में हूँ, जहाँ यह ABCD के लिए interspacing के बारे में कहते हैं .....

सकता है किसी को भी समझाओ कि यहाँ क्या हो रहा है?

धन्यवाद (अपनी भाषा इस में हमारे लिए प्रदर्शन किया गया के रूप में जावा के रूप में चिह्नित है, इसलिए यदि किसी को भी किसी भी कोड उदाहरण तैनात वे देख सकते हैं कि यह उस भाषा में था)

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

यहाँ है कोड:

यह ई पर लग रहा है:

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

फ्लोयड-Warshall एल्गोरिथ्म निम्नलिखित करता है एएच नोड (k) और फिर प्रत्येक i, j के लिए प्रत्येक में दिखता है, यदि i से k से पहले और k से j से पहले यह छोटा रास्ता हो सकता है।

तो यह दिखता है:

"i से j मेरे वर्तमान में कम से कम पथ की लंबाई L0 की है, i से k करने के लिए अपने वर्तमान कम से कम पथ की लंबाई L1 की है, k से j करने के लिए अपने वर्तमान कम से कम पथ की लंबाई की है L2।

क्या होगा यदि मैं एक नया पथ के लिए वर्तमान में कम से कम पथ i to k और k to j गठबंधन? इस नए मार्ग i to k to j मेरी वर्तमान में कम से कम पथ 0 की तुलना में कम है? यदि हां, तो यह लंबाई L1 और L2 नया कम से कम पथ की लंबाई की गणना करने के जम जाता है। "

इसका मतलब है, kj को i से एक तरह से के लिए एक संभावित रोकने से अधिक बिंदु है।

Answer 2

Floyd- Warshall एक dynamic programming समस्या है

यह 2-आयामी संस्करण में यह लिखने के लिए लगभग मानक (और आसान) है:।

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

, लेकिन शायद यह आप 3 आयामी संस्करण के साथ यह चित्र में मदद करता है, ताकि आप सभी राज्यों और अधिक स्पष्ट रूप से देख सकते हैं:

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

राज्यों के एक से थोड़ा गहरा स्पष्टीकरण Algorithmist में पाया जाता है।