重みつきグラフ

重みつきグラフは、辺に距離、時間、費用などの数値（重み）を付けたグラフです。

■ 試験で押さえるポイント

• 最短経路の問題（ダイクストラ法など）のモデルになります。

• 道路の地図やネットワークの経路を表すのに使います。

■ 過去問での着眼点

重みの合計が最小になる経路を求める問題と結び付けて押さえます。

例: 駅を頂点、所要時間を重みとして、目的地までの最短の経路を求めます。