SLF Algorithm
最短路アルゴリズム。
SLF: Small Label to the Front
頂点をDequeで管理し、最短路の更新が起きたとき
更新された最短路がキュー先頭の最短路以下なら先頭に追加
そうでなければ末尾に追加する
計算量についてはよくわかってないとのこと、最悪ケースでは指数かもしれない
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;
}
if deque.is_empty() || d2 <= dist[deque0] { deque.push_front(v);
} else {
deque.push_back(v);
}
}
}
dist
}
参考