Dijkstra algorithm (ダイクストラ アルゴリズム)。 "全てのEdge(辺)のWeight(重み)が非負の場合"に、 重みつき有向グラフ G=(V,E) に対する Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。実装の仕方により、Dijkstra al…

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 (単一始点最短路問題)、を解くことができる。 "始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行う。…

Relaxation (緩和法)。 各Vertexの最短路重みの上界： d[v] 各vertex v∈V に関し、始点 sから、vへの最短路の重みに関する 上界 d[v]を、vertexの属性として管理する。 d[v] ：最短路の推定値(shortest-path estimate) 初期化：Initialize-Single-Source(G,s…

"Shortest-Path Problem (最短路問題)"とは、 "最短路(shortest path)"を求める問題。 『vertex(頂点) u からvertex vへの最短路』とは 『経路重みが、最短路重みに等しい経路』。 。 ※ここで、"辺重み","経路重み", "最短路重み"の定義は以下：[辺重み] Edg…

Topological Sort (トポロジカル ソート)： Directed Acyclic Graph（DAG：非循環有向グラフ) G=(V,E)に対し、 全vertexに対する線形順序で、G が edge (u, v) を含んでいれば、線形順序の中で uがvより先に現れる形へのVertex Sort。 Topological-Sort(G) 1…

Depth-First Search (深さ優先検索). (Reference："Introduction to Algorithms, Second Edition") 可能ならば常に"より深く"、グラフを探索する。 未探索の edge(辺) が残されている vertex(頂点) の中で、最後に発見した頂点vのedgeを探索。vのedge全て全…

Edward F. Moore の Breadth First Seach Algorithm。[Original]Edward F. Moore, "The shortest path through a maze": Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959. Algorithm…

最近、"新しいクラス"のグラフ理論(Graph Theory)の構築／取扱いを進行。 それに関連し、共有のため、 離散数学／グラフ理論／組合せ最適化、等、の基礎や関連Topicsも紹介していこうと思います。