ツンデレで学ぶダイクストラ法

Nawashiro

ふ、ふん。別にアンタのために書いてあげるわけじゃないんだからね！勘違いしないでよね！ このドキュメントは、ダイクストラ法について解説したものよ。グラフの基本から始めて、最短経路問題を解くためのアルゴリズムを丁寧に説明していくわ。初心者でも理解できるように、図や例をたくさん使って解説するから、安心して読み進めてちょうだい。…べ、別にアンタが理解できるかどうか心配してるわけじゃないんだからね！ ## レジュメ 導入: グラフの基本概念（ノード、エッジ、重み）の説明 隣接行列によるグラフの表現方法 ダイクストラ法の解説: ダイクストラ法の解説 図を用いたアルゴリズムの実行例 アルゴリズムが正しく動作する理由の説明 計算量: ダイクストラ法の計算量の分析 (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