1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// Copyright (C) 2020 Joseph R. Quinn
// SPDX-License-Identifier: MIT

#![feature(const_generics)]

#![allow(incomplete_features)]

use std::cmp::PartialOrd;
use std::ops::{ Add, IndexMut };

/// Generic implementation of the Floyd-Warshall algorithm
/// for finding the shortest paths in a weighted graph.
pub fn floyd_warshall<N, M, V>(graph: &N, size: usize) -> N
where
    V: Add<Output=V> + PartialOrd + Copy + Clone + Sized,
    M: IndexMut<usize, Output=V> + Clone + Sized,
    N: IndexMut<usize, Output=M> + Clone + Sized
{
    let mut result_graph = graph.clone();

    for k in 0..size {
        for i in 0..size {
            for j in 0..size {
                if result_graph[i][j] > result_graph[i][k] + result_graph[k][j] {
                    result_graph[i][j] = result_graph[i][k] + result_graph[k][j];
                }
            }
        }
    }

    result_graph
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_floyd_warshall_vector() {
        let graph = vec![
            vec![0.0, f32::INFINITY, -2.0, f32::INFINITY],
            vec![4.0, 0.0, 3.0, f32::INFINITY],
            vec![f32::INFINITY, f32::INFINITY, 0.0, 2.0],
            vec![f32::INFINITY, -1.0, f32::INFINITY, 0.0]
        ];

        let expected = vec![
            vec![0.0, -1.0, -2.0, 0.0],
            vec![4.0, 0.0, 2.0, 4.0],
            vec![5.0, 1.0, 0.0, 2.0],
            vec![3.0, -1.0, 1.0, 0.0]
        ];

        let length = graph.len();

        let calculated = floyd_warshall(&graph, length);

        assert_eq!(expected, calculated);
    }
}