タグ: 幅優先探索

← タグ一覧

• グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する本グラフを隣接行列と隣接リストで表し、幅優先探索が最短の辺数を与えること、深さ優先探索が有向閉路を検出することを証明する。さらに非負重みの下でダイクストラ法の正当性を示し、優先度付きキューによる O(E log V) を導く。情報科学アルゴリズムとデータ構造学部グラフ幅優先探索深さ優先探索ダイクストラ法最短経路約 43 分