このドキュメントは、ツンデレっ娘がダイクストラ法について解説するものです。初心者でも理解できるように、図や例をたくさん使って解説します。 グラフの基本から始めて、最短経路問題を解くためのアルゴリズムを丁寧に説明しています。 ## レジュメ 導入: グラフの基本概念（ノード、エッジ、重み）の説明 隣接行列によるグラフの表現方法 ダイクストラ法の解説: ダイクストラ法の解説 図を用いたアルゴリズムの実行例 アルゴリズムが正しく動作する理由の説明 計算量: ダイクストラ法の計算量の分析 (O(n^2)) プログラム例: ナイーブな疑似コード Priority First Search (PFS) というダイクストラ法の最適化手法の紹介 注意点: 負の重みを持つグラフに対するダイクストラ法の限界 Bellman-Ford 法の紹介 ## 目次 1. 導入 1.1 グラフとはなんですか？ 1.2 グラフってどうやってコンピュータで表現するのですか？ 2. ダイクストラ法の解説 2.1 ダイクストラ法ってなんですか？ 2.2 よくわからないので、図を描いてください 2.3 どうしてこれでうまくいくのですか？ 2.3.1 なんで保証されるのですか？ 3. 計算量 3.1 計算量が気になります 4. プログラム例 4.1 プログラムはどうやって書けばいいですか？ 4.2 実際の実装では何か工夫はありますか？ 5. 注意点 終わりに 著者より: ko-fiから買ってくれると手数料が安いです。値段は変わりませんが… https://ko-fi.com/s/06da60c723