グラフアルゴリズムポータル

1導入どうにゅう

このポータルでは、グラフの基本概念きほんがいねんから探索たんさく、最短路問題さいたんろもんだい、ダイクストラ法ほうへ進すすむ学習順序がくしゅうじゅんじょを説明せつめいする。

グラフアルゴリズムでは、まず頂点ちょうてん・辺へん・隣接りんせつ・道みち・距離きょりを定義ていぎする。次つぎにDFSとBFSによって到達可能性とうたつかのうせいを判定はんていし、BFSが無重むおもみグラフの最短距離さいたんきょりを計算けいさんする理由りゆうを理解りかいする。その後ご、辺へんの重おもみを含ふくむ最短路問題さいたんろもんだいを定式化ていしきかし、重おもみが非負ひふである場合ばあいの解法かいほうとしてダイクストラ法ほうを学習がくしゅうする。

2学習目標がくしゅうもくひょう

• 無重むおもみグラフと重おもみ付つきグラフの相違そういを説明せつめいできる。
• 到達可能性とうたつかのうせいの判定はんていと最短路さいたんろの計算けいさんを区別くべつできる。
• 無重むおもみ最短路さいたんろにはBFSを、非負ひふの重おもみをもつ最短路さいたんろにはダイクストラ法ほうを選択せんたくできる。
• 各手法かくしゅほうの前提条件ぜんていじょうけんを確認かくにんし、適用範囲てきようはんいを説明せつめいできる。

3学習順序がくしゅうじゅんじょ

3.11. グラフの基本きほん

探索たんさくと最短路さいたんろの共通言語きょうつうげんごとなる頂点ちょうてん、辺へん、隣接りんせつ、道みち、距離きょりを確認かくにんする。

3.22. DFSとBFS

DFSとBFSによる到達可能性とうたつかのうせいの判定はんていを学習がくしゅうする。BFSについては、各辺かくへんの費用ひようが等ひとしい無重むおもみグラフにおける最短性さいたんせいも確認かくにんする。

3.33. 最短路問題さいたんろもんだい

道みちの長ながさを辺数へんすうで測定そくていする場合ばあいと、辺へんの重おもみの総和そうわで測定そくていする場合ばあいを区別くべつする。これにより、BFSと重おもみ付つき最短路さいたんろアルゴリズムの適用条件てきようじょうけんを整理せいりする。

3.44. ダイクストラ法ほう

辺へんの重おもみがすべて非負ひふであるという前提ぜんていのもとで、ダイクストラ法ほうが暫定距離ざんていきょりを確定かくていする原理げんりを学習がくしゅうする。負ふの重おもみを含ふくむグラフには、この手法しゅほうを適用てきようできない。

4手法選択しゅほうせんたくの基準きじゅん