DAG-Shortest-Paths algorithm (有向非巡回グラフ 最短路アルゴリズム)。有向非巡回グラフ(DAG: Directed Acyclic Graph)の最短路を求めるアルゴリズム。 DAG G =(V,E)のEdgeに対し次の操作を行う：1. DAG G に対し、Topological sortを行い、 線形順序を与…

Bellman-Ford Algorithm (ベルマン・フォード アルゴリズム)。 "負の重みの辺を許す"一般的な、 Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。 "始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行う。…