フロイド・ワーシャル法

ノード間の最短距離を計算します。

- DPの一つ 

- $O(n^3)$

- 無向グラフ

![IMG_2817.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/241774/3b98fd77-e29e-abe7-68e6-1dbf09ab77ca.jpeg)


```Rust
use std::cmp::{max, min};

fn all_shortest_paths(mut d: Vec<Vec<Vec<i64>>>, n: usize) {
    for k in 0..n {
        for i in 0..n {
            for j in i+1..n {
                d[k+1][i][j] = min(
                    d[k][min(i, k)][max(i, k)] + d[k][min(k, j)][max(k, j)],
                    d[k][i][j]);
            }
        }

        for i in 0..n {
            println!("{:?}", d[k+1][i]);
        }
        println!();
    }
}

fn main() {
    let inf = i64::max_value() / 2;

    // 初期化
    let n = 5;
    let mut d = vec![vec![vec![0; n]; n]; n+1];
    d[0][0][1] = 1;
    d[0][0][2] = 2;
    d[0][0][3] = inf;
    d[0][0][4] = inf;
    d[0][1][2] = 5;
    d[0][1][3] = 1;
    d[0][1][4] = inf;
    d[0][2][3] = 4;
    d[0][2][4] = 2;
    d[0][3][4] = 1;

    for i in 0..n {
        println!("{:?}", d[0][i]);
    }
    println!();

    all_shortest_paths(d, n);
}
```

## 隣接行列の片側も使う場合

より簡単にかけます。

```Rust
use std::cmp::min;

// // https://atcoder.jp/contests/abc021/submissions/5777748
// ↓
use std::io::prelude::*;
fn input<T>() -> T
    where T: std::str::FromStr {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}
// ↑
// // https://atcoder.jp/contests/abc021/submissions/5777748

static INF: i64 = 100_000_000;

fn main() {
    let n = input::<usize>(); // ノード数
    let m = input::<usize>(); // パス数
    let v = (0..m)            // パス (ノードa, ノードb, パス(a, b)のコスト)
        .map(|_| (input::<usize>()-1, input::<usize>()-1, input()))
        .collect::<Vec<(_, _, i64)>>();

    let mut d = vec![vec![INF; 100]; 100];

    for  i in 0..n {
        d[i][i] = 0;
    }

    for &(a, b, c) in &v {
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                d[i][j]=min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for &(a, b, c) in &v {
        println!("({}, {}) において {} -> {}",a+1, b+1, c, d[a][b]);
    }
}
```

![F.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/241774/de078df9-d79a-ec84-ca44-0c557c50986c.png)

```入力
3 3
1 2 1
1 3 1
2 3 3
```

```出力
(1, 2) において 1 -> 1                                                             
(1, 3) において 1 -> 1                                                             
(2, 3) において 3 -> 2
```

## 最短パスとして使われるパスの数

AtCoder にて２回程見たことがあります。

[abc051 D問題](https://abc051.contest.atcoder.jp/tasks/abc051_d)など

```Rust
#![allow(unused_imports)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(dead_code)]
#![allow(unused_variables)]

use std::collections::HashSet;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::cmp::{max, min};
use std::mem::swap;
use std::io::prelude::*; // input()

fn input<T>() -> T
    where T: std::str::FromStr {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

static INF: usize = 1_000_000;

fn main() {
    let n = input::<usize>();
    let m = input::<usize>();
    let abc = (0..m)
        .map(|_| (input::<usize>()-1,input::<usize>()-1,input::<usize>()))
        .collect::<Vec<_>>();

    let mut d = vec![vec![INF; 100]; 100];
    for i in 0..n {
        d[i][i] = 0;
    }
    for &(a, b, c) in &abc {
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    // 追加分
    let mut ans = m;

    for &(a, b, c) in &abc {
        let shortest = || {
            for j in 0..n {
                if d[j][a] + c == d[j][b]  {
                   return true;
                }
            }
            false
        };
        if shortest() {
            ans-=1;
        }
    }
    println!("{}", ans);
    // 追加分
}
```



# 参考

[wiki](https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95)

[PythonのNetworkXで重み付きグラフの表示](https://qiita.com/skyknsk/items/496116af2f1f8e88c616)

[AtCoder ABC051 D問題](https://atcoder.jp/contests/abc051/tasks/abc051_d)