D’Esopo-Pape Algorithm
最短路アルゴリズム。負辺のあるグラフにおいてもそこそこ高速に最短路を求めることができる。
負閉路が含まれてはいけない。
このアルゴリズムでは、次に見る頂点をDequeで管理する（SPFAに類似）
それぞれの頂点について以下の状態を持つ
code:text
usedv: これまでに最短路が更新されたことがあるか 最短路を更新するとき、Dequeに入っていない頂点であればDequeに入れる
このとき、これまで最短路が更新されたことがなければ末尾に、そうでなければ先頭に入れる（SPFAと異なる点）
感想
SPFAよりちょっと速い（最悪ケースはSPFAの方が良い）
謎ヒューリスティックが謎すぎて謎
in_queueとusedをひとつにまとめる実装が主流らしい
コード
code:rust
let mut deque = std::collections::VecDeque::new();
deque.push_back(start);
while let Some(u) = deque.pop_front() {
let d2 = d.saturating_add(w);
continue;
}
continue;
}
deque.push_front(v);
} else {
deque.push_back(v);
}
}
}
dist
}
参考
そこそこ速いよ！