Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
641 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.5k puan) tarafından  | 641 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,282 soru
21,821 cevap
73,503 yorum
2,520,428 kullanıcı