高度なアルゴリズム：グラフと最短経路

グラフ表現

駅や道路、サービス間接続のような点と辺を持つ問題はグラフで表します。頂点をVecの添字、辺を隣接リストで管理します。

Dijkstra法

重みが0以上のグラフで最短距離を求めます。BinaryHeapで距離が小さい頂点から処理します。

use std::{cmp::Reverse,collections::BinaryHeap};
fn dijkstra(g:&[Vec<(usize,u64)>],s:usize)->Vec<u64>{
 let mut d=vec![u64::MAX;g.len()];let mut h=BinaryHeap::new();
 d[s]=0;h.push(Reverse((0_u64,s)));
 while let Some(Reverse((c,v)))=h.pop(){if c!=d[v]{continue;}
  for &(to,w) in &g[v]{if let Some(x)=c.checked_add(w){if x<d[to]{d[to]=x;h.push(Reverse((x,to)));}}}
 } d
}

時間計算量はおおむねO((V+E)log V)、空間計算量はO(V+E)。負の重みには使えません。

演習：最短距離