1. ダイクストラ法
use std::collections::BinaryHeap;
const INF: usize = 1 << 61;
struct Graph {
edges: Vec<Vec<(usize, i64)>>, // adjacent list
n: usize
}
impl Graph {
fn new(n: usize) -> Self {
Graph {
edges: vec![Vec::new(); n],
n: n
}
}
fn add_costs(&mut self, from: usize, to: usize, cost: i64, directed: bool) {
if directed {
self.edges[from].push((to, cost));
} else {
self.edges[from].push((to, cost));
self.edges[to].push((from, cost));
}
}
fn dijkstra_search(&self, start: usize) -> (Vec<i64>, Vec<usize>) {
let mut dist: Vec<i64> = vec![INF; self.n]; // Dijkstraなのでi64ではなくusizeの方がいいかも
let mut visited: Vec<bool> = vec![false; self.n];
let mut prev: Vec<usize> = vec![INF as usize; self.n]; //nodeを格納するのにusizeでないの気持ち悪い
dist[start] = 0;
let mut que: BinaryHeap<(i64, usize)> = BinaryHeap::new();
que.push((0, start));
while let Some((_, v)) = que.pop() {
if visited[v] {
continue
}
visited[v] = true;
for edge in &self.edges[v] {
let (u, cost) = *edge;
if visited[u] {
continue
}
if dist[u] > dist[v] + cost {
dist[u] = dist[v] + cost;
prev[u] = v;
que.push(( -dist[u], u));
}
}
}
return (dist, prev)
}
fn dijkstra_shortest_path(&self, start: usize, goal: usize) -> Vec<usize> {
let (dist, prev) = self.dijkstra_search(start);
let mut shortest_path: Vec<usize>= vec![];
let mut node = goal;
while node != INF {
shortest_path.push(node);
node = prev[node];
}
shortest_path.reverse();
return shortest_path
}
}
2.1. ベルマンフォード法 近接リスト
const INF: i64 = 1 << 61;
// adjacent list
struct Graph {
edges: Vec<(usize, usize, i64)>, // adjacent list
n: usize
}
impl Graph {
fn new(n: usize) -> Self {
Graph {
edges: vec![],
n: n
}
}
fn add_costs(&mut self, from: usize, to: usize, cost: i64, directed: bool) {
if directed {
self.edges.push((from, to, cost));
} else {
self.edges.push((from, to, cost));
self.edges.push((to, from, cost));
}
}
fn bellmanford_search(&self, start: usize) -> Vec<i64> {
let mut dist: Vec<i64> = vec![INF; self.n];
dist[start] = 0;
loop {
let mut update: bool = false;
for edge in &self.edges {
let (from, to, cost) = *edge;
if (dist[from] != INF) & (dist[to] > dist[from] + cost) {
dist[to] = dist[from] + cost;
update = true;
}
}
if !update {
break;
}
}
return dist
}
fn bellmanford_search_negative_cycle(&self, start: usize) -> (bool, Vec<i64>) {
// (true, dist) なら負の閉路を含む
let mut dist: Vec<i64> = vec![INF; self.n];
dist[start] = 0;
for i in 0..self.n {
for &(from, to, cost) in &self.edges{
if (dist[from] != INF) & (dist[to] > dist[from] + cost) {
dist[to] = dist[from] + cost;
if i == self.n - 1{
return (true, dist);
}
}
}
}
return (false, dist);
}
}
2.2. ベルマンフォード法 近接行列
//adjacent matrix
struct Graph {
edges: Vec<Vec<(usize, i64)>>, // adjacent matrix
n: usize
}
impl Graph {
fn new(n: usize) -> Self {
Graph {
edges: vec![Vec::new(); n],
n: n
}
}
fn add_costs(&mut self, from: usize, to: usize, cost: i64, directed: bool) {
if directed {
self.edges[from].push((to, cost));
} else {
self.edges[from].push((to, cost));
self.edges[to].push((from, cost));
}
}
fn bellmanford_search(&self, start: usize) -> Vec<i64> {
let mut dist: Vec<i64> = vec![INF; self.n];
dist[start] = 0;
let mut update: bool = true;
while update {
update = false;
for from in 0..self.n {
for edge in &self.edges[from] {
let (to, cost) = *edge;
if dist[to] > dist[from] + cost {
dist[to] = dist[from] + cost;
update = true;
}
}
}
}
return dist
}
fn bellmanford_search_negative_cycle(&self, start: usize) -> (bool, Vec<i64>) {
// (true, dist) なら負の閉路を含む
let mut dist: Vec<i64> = vec![INF; self.n];
dist[start] = 0;
let mut counter = 0;
let mut update: bool = true;
while update {
update = false;
for from in 0..self.n {
for edge in &self.edges[from] {
let (to, cost) = *edge;
if (dist[from] != INF) & (dist[to] > dist[from] + cost) {
dist[to] = dist[from] + cost;
update = true;
counter += 1;
}
}
}
if counter >= self.n * self.n {
return (true, dist);
}
}
return (false, dist);
}
}
3. ワーシャルフロイド法
const INF: i64 = 1 << 61;
use std::cmp::min;
struct GraphWarshalFloyd {
edges: Vec<Vec<i64>>,
n: usize
}
impl GraphWarshalFloyd {
fn new(n: usize) -> Self {
GraphWarshalFloyd {
edges: vec![vec![INF; n]; n],
n: n
}
}
fn add_costs(&mut self, from: usize, to: usize, cost: i64, directed: bool) {
if directed {
self.edges[from][to] = cost;
} else {
self.edges[from][to] = cost;
self.edges[to][from] = cost;
}
}
fn warshalfloyd(&self) -> (bool, Vec<Vec<i64>>) {
// (true, dist) なら負の閉路を含む
let mut dist: Vec<Vec<i64>> = vec![vec![INF; self.n]; self.n];
for i in 0..self.n {
for j in 0..self.n {
dist[i][j] = self.edges[i][j]
}
}
for i in 0..self.n {
for j in 0..self.n {
for k in 0..self.n {
if (dist[j][i] != INF) & (dist[i][k] != INF) {
dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k])
}
}
}
}
let mut has_negative_cycle = false;
for i in 0..self.n {
if dist[i][i] < 0 {
has_negative_cycle = true;
}
dist[i][i] = 0;
}
return (has_negative_cycle, dist)
}
}