SLF Algorithm

最短路アルゴリズム。

SLF: Small Label to the Front

SPFAやD’Esopo-Pape Algorithmと同様のlabel correcting algorithm

頂点をDequeで管理し、最短路の更新が起きたとき

更新された最短路がキュー先頭の最短路以下なら先頭に追加

そうでなければ末尾に追加する

計算量についてはよくわかってないとのこと、最悪ケースでは指数かもしれない

code:rust

fn sssp_slf(graph: &Vec<(usize, i64)>, start: usize) -> Vec<i64> {

let mut in_queue = vec!false; graph.len();

let mut deque = std::collections::VecDeque::new();

diststart = 0;

in_queuestart = true;

deque.push_back(start);

while let Some(u) = deque.pop_front() {

in_queueu = false;

let d = distu;

for &(v, w) in &graphu {

let d2 = d.saturating_add(w);

if distv <= d2 {

continue;

}

distv = d2;

if in_queuev {

continue;

}

in_queuev = true;

if deque.is_empty() || d2 <= dist[deque0] {

deque.push_front(v);

} else {

deque.push_back(v);

}

dist

}

参考