グラフ
ワーシャル＝フロイド法とは 今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル＝フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマ…
有向グラフとは 有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は の形式を持ち, 頂点 から頂点 へはコスト で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません. 今回…
木構造の距離を求める問題演習として, AtCoder Beginner Contest 070 の D 問題の解説をしてみます. 問題はこちら abc070.contest.atcoder.jp
グラフの一種である木構造での距離を求めるアルゴリズムを考えます. グラフとは 詳しくは グラフ理論 - Wikipedia などの記述をご参照ください. グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを…
