Floyd-Warshall (All-Pairs Shortest Paths)

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {

}

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {

    // Core idea: grow the set of allowed intermediate vertices one at a time.
    // After iteration k, dist[i][j] is the best path using only 0..k as stops.
}

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {
    n := len(dist)

    // Core idea: grow the set of allowed intermediate vertices one at a time.
    // After iteration k, dist[i][j] is the best path using only 0..k as stops.
    for k := 0; k < n; k++ {
    }
}

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {
    n := len(dist)

    // Core idea: grow the set of allowed intermediate vertices one at a time.
    // After iteration k, dist[i][j] is the best path using only 0..k as stops.
    for k := 0; k < n; k++ {
        // With k now allowed as a waypoint, retry every source/target pair.
    }
}

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {
    n := len(dist)

    // Core idea: grow the set of allowed intermediate vertices one at a time.
    // After iteration k, dist[i][j] is the best path using only 0..k as stops.
    for k := 0; k < n; k++ {
        // With k now allowed as a waypoint, retry every source/target pair.
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
            }
        }
    }
}

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {
    n := len(dist)

    // Core idea: grow the set of allowed intermediate vertices one at a time.
    // After iteration k, dist[i][j] is the best path using only 0..k as stops.
    for k := 0; k < n; k++ {
        // With k now allowed as a waypoint, retry every source/target pair.
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                // Is detouring i -> k -> j shorter than the best i -> j so far?
            }
        }
    }
}

// dist[i][j] holds the edge weight from i to j, or a large sentinel for "no
// edge" (use something like math.MaxInt64/2 so k-path sums don't overflow).
// floydWarshall relaxes it in place into all-pairs shortest distances.
func floydWarshall(dist [][]int) {
    n := len(dist)

    // Core idea: grow the set of allowed intermediate vertices one at a time.
    // After iteration k, dist[i][j] is the best path using only 0..k as stops.
    for k := 0; k < n; k++ {
        // With k now allowed as a waypoint, retry every source/target pair.
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                // Is detouring i -> k -> j shorter than the best i -> j so far?
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
}