Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
237 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 (24.9k puan) tarafından  | 237 kez görüntülendi

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.2k puan) tarafından 
19,731 soru
21,419 cevap
71,971 yorum
306,180 kullanıcı