Bu ders için video bulunmamaktadır.
Bu derse başlamak veya ilerlemenizi kaydetmek için lütfen giriş yapın veya kayıt olun.
Ders İçeriği
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) |