Floyd-Warshall-Algorithmus Logik - Stuck

Ich versuche, diese Logik zu verstehen, was ist Los mit den Nachbarschaft-matrix, aber ich bin massivley verwirrt, wo er sagt über interspacing für a b c d........

Könnte jemand erklären, was hier Los ist?

Danke
(tagged as java als die Sprache, dies zeigte uns, also wenn jemand gepostet alle code-Beispiele, die Sie sehen konnte, war es in dieser Sprache)

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

Hier ist der code:

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];
  • Floyd-Warshall ist eine der typischen "DP-algo", zusammen mit Levenhstein die Edit-Distanz und die "0-1 Knapsack". Um es zu verstehen muss man verstehen, was "Dynamische Programmierung" ist über (die meisten Programmierer, die noch keine CS Grad nicht wissen, etwas über die DP). Der Wikipedia-Eintrag zum Thema ist gut: en.wikipedia.org/wiki/Dynamic_programming und ansonsten kann man versuchen zu beteiligen, die in ein paar online-Wettbewerb, der (wie TopCoder), wo in der Regel eine ganze Menge der Probleme brauchen eine DP-Lösung.
InformationsquelleAutor stan | 2010-04-22
  1. 7

    Floyd-Warshall, ist ein dynamische Programmierung problem.

    Es ist fast schon standard (und einfacher) zu schreiben, in der 2-dimensionalen version:

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

    aber vielleicht hilft es Ihnen, das Bild mit der 3-dimensionalen version, so können Sie sehen, alle Staaten, explizit:

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

    einem leicht tieferen Erklärung der Zustände finden Sie in Algorithmist.

    • In Sie die Letzte Zeile im code sollte es sein, dist[k-1][i][j] anstelle von dist[i][j] ich denke,
    InformationsquelleAutor Larry
  2. 4

    Den Floyd-Warshall-Algorithmus ist die folgende:

    Sieht es an jedem Knoten (k) und schaut dann in jeder k-iteration für jede i, j auch, ob es einen kürzeren Pfad von erst von i zu k und dann von k zu j.

    So sieht es aus:

    "Meine derzeit kürzeste Weg von i zu j ist die Länge L0 meine derzeit kürzeste Weg von i zu k ist die Länge L1 meine derzeit kürzeste Weg von k zu j ist die Länge L2.

    Was passiert, wenn ich kombinieren, die derzeit kürzesten Wege i to k und k to j zu einem neuen Weg? Ist dieser neue Pfad i to k to j kürzer als meine derzeit kürzeste Weg i to j? Wenn dem so ist, Reichert es sich in den Längen L1 und L2 zum berechnen der Länge des neuen kürzesten Pfad."

    Das bedeutet, k ist ein potentieller stop-over Punkt für einen Weg aus i zu j.

    InformationsquelleAutor phimuemue
Schreibe einen Kommentar