Motivation

Dijkstra, en kısa mesafesi zaten bilinen bir düğüm (vertex) kümesini genişletir. Her zaman henüz kesinleşmemiş en yakın düğümü kesinleştirir, ardından bu düğümü komşularına olan mesafeleri iyileştirmek (gevşetmek - relax) için kullanır.

Neden Dijkstra öğrenmelisiniz?

• Her yerde: GPS yönlendirme, ağ paketi yönlendirme ve her türlü en düşük maliyetli yol bulma.
• İşe yarayan açgözlü (greedy): Ağırlıklar negatif olmadığı sürece, kanıtlanabilir şekilde optimumu veren açgözlü bir seçimin temiz bir örneğidir.
• Temel: Gevşetme (relaxation) fikri A* ve diğer en kısa yol algoritmalarında tekrar karşımıza çıkar.

Önemli: Dijkstra negatif ağırlık olmadığını varsayar. Negatif kenarlar, bir sonraki ders olan Bellman-Ford'u gerektirir.