Ağırlıklı graflarda en kısa yol ve minimum kapsayan ağaç bulma algoritmaları.
Dijkstra Algoritması
Tek kaynaktan tüm düğümlere en kısa yolları bulan algoritma.
Çalışma Prensibi:
- Başlangıç düğümünün uzaklığını 0 yap
- En küçük uzaklıktaki düğümü seç
- Komşularının uzaklıklarını güncelle
- Tüm düğümler işlenene kadar tekrarla
Zaman Karmaşıklığı:
- O(E log V) - Öncelik kuyruğu ile
- Negatif ağırlıklı kenarlarla çalışmaz
Prim Algoritması
Minimum Kapsayan Ağaç (MST) bulan açgözlü algoritma.
Çalışma Prensibi:
- Rastgele bir düğümden başla
- MST'deki düğümlerden en küçük ağırlıklı kenarı seç
- Kenarı ve düğümü MST'ye ekle
- Tüm düğümler eklenene kadar tekrarla
Kruskal Algoritması
Kenarları ağırlıklarına göre sıralayarak MST bulan algoritma.
Çalışma Prensibi:
- Tüm kenarları ağırlıklarına göre sırala
- En küçük ağırlıklı kenarı al
- Döngü oluşturmuyorsa MST'ye ekle
- V-1 kenar eklenene kadar tekrarla
Karşılaştırma
| Algoritma | Amaç | Zaman Karmaşıklığı |
|---|---|---|
| Dijkstra | En Kısa Yol | O(E log V) |
| Prim | MST | O(E log V) |
| Kruskal | MST | O(E log E) |