Çizgeler Teorisi - Dijkstra Algoritmasının performansı

Question

Cizgeler icin Dijkstra algoritm nedir? Ne kadar etkili bir yontem? Performansini buyuk $\mathcal O$ notasyonu ile gosteriniz.

                                       

Comments

ya ben bunu veri bilimine tasimak istiyorum aslinda

---

emin olamadım, ikisini de seçebilsek keşke.

Answer 1

Dijkstra algoritmasi, bir ciygede iki kose arasindaki en kisa yolu verir. En kotu ihtimalle (Eger fibbonacci heap ile duygun implemente edilmis ise)

$|E|+|V|\log|V|$ ile calisir. Burada $|E|$ ciygenin kenar sayisi, $|V|$ ise kose sayisi.

Algoritmanin adimlari:

1. Butun koseleri gidilmemis olarak isaretle
2. Butun koselere bir uzaklik degeri ata. Baslangic kosesine $0$ digerlerine ise $\infty$ ata. Guncel kose, baslangic kosesi olsun
3. Guncel kosenin ziyaret edilmemis komsularina bak ve uzakliklarini hesapla (kendi uzaklik degerim+komsuma olan uzakligim). Eger hesaplanan uzaklik onceki atanmis degerden kucuk ise atanmis degeri yeni uzaklikla degistir.
4. Guncel kosenin komsularina bakildiktan sonra guncel kosesyi gidilmis olarak isaretle.
5. Eger Bitis kosesi ziyaret edilmis ise algoritmayi durdur
6. Gidilmemis koselerden uzakligi en kucuk olani sec ve algoritmaya 3. adimdan devam et

Bunun disinda bir de $A^*$ algoritmasi vardir ayni sorun icin gelistirilmistir ama o da baska bi soru olsun.