テクノロジ系 / アルゴリズムとプログラミング
最短経路探索
最短経路探索は、グラフ上である頂点から別の頂点までの合計コストが最小になる経路を求める処理です。
もう少し詳しく
道路網、通信経路、配送経路などを、頂点と辺と重みで表して考えます。辺の重みが非負ならダイクストラ法、負の重みを扱うならベルマンフォード法など、条件によって使う方法が変わります。
試験での見方
例：駅Aから駅Dまで、A→B→Dが15分、A→C→Dが12分なら、後者が最短経路になります。
テクノロジ系 / アルゴリズムとプログラミング
最短経路探索は、グラフ上である頂点から別の頂点までの合計コストが最小になる経路を求める処理です。
道路網、通信経路、配送経路などを、頂点と辺と重みで表して考えます。辺の重みが非負ならダイクストラ法、負の重みを扱うならベルマンフォード法など、条件によって使う方法が変わります。
例：駅Aから駅Dまで、A→B→Dが15分、A→C→Dが12分なら、後者が最短経路になります。
最短経路の問題では、現在の暫定距離、確定済み頂点、更新された距離を段階ごとに表にします。単純な辺数ではなく、重みの合計で比較する点に注意しましょう。