Dijkstra’nın algoritması Prim’in algoritmasına çok benzer. En kısa yol ağacı, kenardan kenara inşa edilir. Ağaca dahil edilmiş olan köşelerin kümesi ve henüz dahil edilmemiş köşelerin kümesi olmak üzere 2 kümemiz vardır.
Açgözlü Seçim, iki seti birbirine bağlayan kenarı seçmek ve kaynaktan henüz dahil olmayan köşeleri içeren kümeye en küçük ağırlıklı yolu seçmektir.
Açgözlü Seçim, iki seti birbirine bağlayan kenarı seçmek ve kaynaktan henüz dahil olmayan köşeleri içeren kümeye en küçük ağırlıklı yolu seçmektir.
- Başlangıç olarak sadece başlangıç düğümünün en kısa yolu bilinir. (0 dır.)
- Tüm düğümlerin maliyeti bilinene kadar devam et.
- O anki bilinen düğümler içerisinden en iyi düğümü şeç. (en az maliyetli düğümü seç, daha sonra bu düğümü bilinen düğümler kümesine ekle)
- Seçilen düğümün komşularının maliyetlerini güncelle.
Paylaş
Dijkstra Algoritması(Dijkstra’s Shortest Path)
4/
5
Oleh
Kubra Cosar
