はじめに
最短経路を求めるアルゴリズムとして有名なダイクストラ法をRustで実装しました。ダイクストラ法は隣接行列を用いるとO(|V|^2)ですが、優先度付きキューを利用するとO(|E| log |V|)に高速化できます。すごい（小並感）。
BinaryHeapについて
Rustのstd::collections::BinaryHeapを利用します。そのまま利用すると最大値からpopされます。ダイクストラ法では最小値が欲しいので、実装ではpushするときに-1を掛けるようにします。
実装
実装はプログラミングコンテスト攻略のためのアルゴリズムとデータ構造
隣接行列を用いた実装
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
type Graph = Vec<Vec<(usize,usize)>>;
fn dijkstra(s:usize,g:Graph){
let mut d = vec![usize::max_value();g.len()];
d[s] = 0;
let mut p:Vec<isize> = vec![-1;g.len()];
// white=-1, gray=0, black=1
let mut color:Vec<isize> = vec![-1;g.len()];
//探索中の頂点から最小である頂点
let mut minnode = 0;
loop {
//探索中の頂点から最小である頂点を探す
let mut mincost = usize::max_value();
for i in 0..g.len(){
if color[i] != 1 && d[i] < mincost {
mincost = d[i];
minnode = i;
}
}
if mincost == usize::max_value() {
//探索終了
break;
}
color[minnode] = 1;
for v in 0..g.len(){
//未確定かつ接続されているノードか判定
if color[v] != 1 && g[minnode].iter().find(|x| x.0 == v).is_some() {
//最小距離が更新されるか判定
if d[minnode] + g[minnode].iter().find(|x| x.0 == v).unwrap().1 < d[v] {
//最小距離の更新
d[v] = d[minnode] + g[minnode].iter().find(|x| x.0 == v).unwrap().1;
p[v] = minnode as isize;
color[v] = 0;
}
}
}
}
for (i,e) in d.iter().enumerate(){
println!("{} {}",i,e);
}
}
fn main() {
let n: usize = read();
let mut G: Graph = vec![Vec::new(); n];
for _i in 0..n {
let u: usize = read();
let k: usize = read();
for _j in 0..k {
let v: usize = read();
let c: usize = read();
G[u].push((v,c));
}
}
dijkstra(0,G);
}オンラインジャッジ：
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&lang=ja
優先度付きキューを用いた実装
use std::io::*;
use std::str::FromStr;
use std::collections::BinaryHeap;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
type Graph = Vec<Vec<(usize,usize)>>;
fn dijkstra(s:usize,g:Graph){
let mut d = vec![isize::max_value();g.len()];
let mut bh = BinaryHeap::new();
// white=-1, gray=0, black=1 whiteで初期化
let mut color:Vec<isize> = vec![-1;g.len()];
d[s] = 0;
//(距離,頂点)
bh.push((0,s));
color[s] = 0;
while !bh.is_empty() {
let f = bh.pop().unwrap();
//最小距離の隣接頂点
let u = f.1;
color[u] = 1;
//最小距離でなければ無視
if d[u] < f.0 * (-1) {
continue;
}
//v(頂点,距離)
for v in g[u].iter() {
//未確定頂点か判定
if color[v.0] != 1 {
//最小距離の更新
if d[v.0] > d[u] + v.1 as isize {
d[v.0] = d[u] + v.1 as isize;
//優先度付きキューへの追加
bh.push( (d[v.0] * (-1), v.0) );
color[v.0] = 0;
}
}
}
}
for (i,e) in d.iter().enumerate(){
println!("{} {}",i,e);
}
}
fn main() {
let n: usize = read();
let mut G: Graph = vec![Vec::new(); n];
for _i in 0..n {
let u: usize = read();
let k: usize = read();
for _j in 0..k {
let v: usize = read();
let c: usize = read();
G[u].push((v,c));
}
}
dijkstra(0,G);
}オンラインジャッジ：
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C&lang=ja
