Motivation

ダイクストラ法は、最短距離が既に判明している頂点の集合を広げていきます。まだ確定していない頂点のうち最も近いものを常に確定させ、それを利用して隣接する頂点への距離を改善（緩和）します。

なぜダイクストラ法を学ぶのか？

• あらゆるところで: GPSのルート検索、ネットワークパケットのルーティング、およびあらゆる最小コストの経路探索。
• 機能する貪欲法: 重みが非負である限り、証明可能に最適解を与える貪欲な選択の明快な例です。
• 基礎: その緩和（relaxation）の考え方は、A*や他の最短経路アルゴリズムにも再登場します。

重要: ダイクストラ法は負の重みがないことを前提としています。負の辺がある場合は、次のコースで扱うベルマン–フォード法が必要です。