graph.wall

\(n\) 頂点有向グラフの各辺に整数コストが与えられた時、 全点対の最小コストを \(O(n^3)\) で求める.

前提

\(d\)\(n \times n\) のテーブル (二重配列) とする.

以下のライブラリはどちらも \(d\) を与えると破壊的に更新して、

graph.wall.rs

use std::cmp::min;
fn wall(d: &mut Vec<Vec<i32>>) {
    let n = d.len();
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                d[i][j] = min::<i32>(
                    d[i][j],
                    d[i][k] + d[k][j]
                );
            }
        }
    }
}

fn main() {
    let mut d = vec![
        vec![0, 1, 1],
        vec![1, 0, 1],
        vec![4, 2, 0]
    ];
    wall(&mut d);
    println!("{:?}", d);
}

graph.wall.cc

void wall(vvi&d) {
  int n = d.size();
  rep (k, n) rep (i, n) rep (j, n)
    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}