Rustで抽象的にダイクストラ法を実装し最短経路探索する

抽象的にダイクストラ法を実装してみました。

例

このような距離付き無向グラフを例に各地点からcへの最短経路を解きます

このグラフを以下のように簡単に表現できます。

dijkstra.rs

    fn main() {
        let r = dijkstra(
            [
                ("a", "b", 1),
                ("b", "c", 2),
                ("c", "d", 3),
                ("d", "a", 4),
            ].into_iter(),
            ["c"].into_iter(),//goal
        );
        for (k, v) in &r {
            println!("地点{}から目的地までの距離は{}。次の経路は地点{}", k, v.1, v.0)
        }
    }

次に進むべきノードと距離が表示されましたね

地点bから目的地までの距離は2。次の経路は地点c
地点dから目的地までの距離は3。次の経路は地点c
地点aから目的地までの距離は3。次の経路は地点b
地点cから目的地までの距離は0。次の経路は地点c

ここでは地点(node)は文字列、距離は整数としました。
しかしnodeはハッシュが生成できるなら、距離も比較と加算減算できるならどのような型でもgenericに対応できます。

距離が浮動小数点、ノードが整数、配列がVecとHashSetである例

        let r = dijkstra(
            vec![
                (0, 1, 1.0),
                (1, 2, 2.0),
                (2, 3, 3.0),
                (3, 0, 4.0),
            ].into_iter(),
            HashSet::from([2]).into_iter(),//goal
        );
        for (k, v) in &r {
            println!("地点{}から目的地までの距離は{}。次の経路は地点{}", k, v.1, v.0)
        }

実装を見てみましょう。

実装

dijkstra.rs

use std::collections::{HashMap};
use std::hash::Hash;
use std::ops::{Add, Sub};
use std::cmp::PartialOrd;

pub fn dijkstra<N, D>(
    edges: impl Iterator<Item=(N, N, D)> + Clone,
    goals: impl Iterator<Item=N>,
) -> HashMap<N, (N, D)>
    where
        D: Add<Output=D> + Sub<Output=D> + PartialOrd + Copy,
        N: Hash + Eq + Copy
{
    //get max distance
    let max_distance = edges.clone().map(|(_, _, d)| d).reduce(|a, b| a + b).unwrap();
    //get nodes
    let mut nodes: HashMap<N, (N, D)> = edges.clone().map(|v| [v.0, v.1].map(|n| (n, (n, max_distance)))).flatten().collect();
    //set goals
    goals.for_each(|ng| nodes.get_mut(&ng).unwrap().1 = max_distance - max_distance);
    //update loop
    while {
        let mut changed = false;
        for (na, nb, d) in edges.clone() {
            let ((_, da), (_, db)) = (nodes.get(&na).unwrap(), nodes.get(&nb).unwrap());
            if *da > (*db + d){
                nodes.insert(na, (nb, *db + d));
                changed = true;
            } else if *db > (*da + d){
                nodes.insert(nb, (na, *da + d));
                changed = true;
            }
        }
        changed
    } {}
    return nodes;
}

あなたの御用のためにお使いください。