Rustでダイクストラ法を実装する

ダイクストラ(Dijkstra)法とは？

グラフの各頂点への最短経路を求めるアルゴリズムです。
(辺の重みが正の場合のみ適用できる)

詳細についてはネットで検索すれば分かりやすく解説しているページが出てくると思いますので、詳細な説明はそちらをご覧になってください。

実装

BinaryHeapを用いて実装しているので、計算量は$O((E+V)\log V)$です。
(Vは頂点の数、Eは辺の数)

let d = Dijkstra::new(n, edge, 0); で初期化し、
let dist = d.distance(i); で頂点への距離、
let path = d.get_path(i); で最短経路を返却します。

コメント軽く説明を追加してあります。

use std::{cmp::Reverse, collections::BinaryHeap};

const INF: usize = 1 << 31;

struct Dijkstra {
    distance: Vec<usize>,
    parent: Vec<usize>,
}

impl Dijkstra {
    // n:usize 頂点の数
    // edge: Vec<Vec<(usize,usize)>> edge[i] = [(2,3), (3,1), (頂点への道,重み)]
    // init:usize どの頂点を起点に考えるか
    pub fn new(n: usize, edge: Vec<Vec<(usize, usize)>>, init: usize) -> Self {
        let mut distance = vec![INF; n];
        let mut parent = vec![INF; n];
        let mut heap = BinaryHeap::new();
        for i in 0..n {
            if i == init {
                // 始点は0
                // BinaryHeapはpopで最大値を取得するので、Reverse()で最小値を取得できるようにする
                heap.push((Reverse(0), i));
            }
            heap.push((Reverse(INF), i));
        }
        while let Some((Reverse(d), target)) = heap.pop() {
            if distance[target] < d {
                // 既にもっと短い経路が見つかってるので無視
                continue;
            }
            distance[target] = d;
            for &(next, cost) in &edge[target] {
                if distance[next] > d + cost {
                    // 短い経路の候補となるので処理を行う
                    distance[next] = d + cost;
                    heap.push((Reverse(distance[next]), next));
                    // ひとつ前の頂点を保存しておく
                    parent[next] = target;
                }
            }
        }
        Self { distance, parent }
    }

    pub fn distance(&self, target: usize) -> usize {
        self.distance[target]
    }

    pub fn get_path(&self, target: usize) -> Vec<usize> {
        let mut current = target;
        let mut res = vec![current];
        while self.parent[current] != INF as usize {
            let next = self.parent[current];
            res.push(next);
            current = next;
        }
        res.reverse();
        res
    }
}

コードと簡易的なテストは以下にのせております。

最後まで読んでいただきありがとうございました！