有向グラフ上の部分集合Sの任意の頂点u, vについて，uからvに到達可能であるときSは強連結である。Sにどの頂点を加えても強連結にできないとき，Sは強連結成分である。有向グラフGについて全ての強連結成分をつぶして一つにすると、グラフはDAGになる。編集中

TOPOLOGICAL-SORT(G) 各頂点 v の終了時刻 v.f を計算するために DFS(G) を呼び出す ある頂点の探索が終了するたびに、この頂点を連結リストの先頭に挿入する return 頂点の連結リスト

入力：有向グラフG, 非負の重み関数 c: E(G) → R_+ および始点 s ∈ V(G) 出力：sからすべての点 v ∈ V(G) への最短パスとその距離、より正確には、 すべての点 v ∈ V(G) に対する p(v) と l(v) ただし、l(v) は最短s-p(v)-パスと 辺(p(v), v)からなる最短s-v…

参考： 線形代数入門 EMANの物理学

s-t-パスの中でk番目に短いものを求める問題をk-最短路問題という。 Priority Queueを使ったダイクストラで実装するのが基本的な解法となる。 参考 Spaghetti Souce