Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
497 kez görüntülendi

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

                                      image 

Lisans Matematik kategorisinde (25.4k puan) tarafından  | 497 kez görüntülendi
ya ben bunu veri bilimine tasimak istiyorum aslinda
emin olamadım, ikisini de seçebilsek keşke.

1 cevap

0 beğenilme 0 beğenilmeme

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.

(1.6k puan) tarafından 
20,239 soru
21,759 cevap
73,399 yorum
2,065,315 kullanıcı