Uğur Dönmez

Dijkstra nın en kısa yol algoritması verilen bir grafikte başlangıç noktasından bitiş noktasına en kısa yoldan nasıl gidilebileceğini hesaplar. Edsger Dijkstra tarafından 1959 yılında tasarlanmıştır.

 

Algoritma :

 

1. Başlangıç noktası hariç bütün köşelerin(node) değerini sonsuz yapın. Başlangıç noktasını 0 yapın.

2. Bütün köşeleri ziyaret edilmemiş(unvisited) olarak işaretleyin. Başlangıç noktasını priority queue a atın.

3. Queue e boşalana kadar, queue nin başındaki köşeyi çekin. Köşeyi ziyaret edilmiş olarak işaretleyin. Köşenin bütün komşuları ziyaret edin. Eğer giderken bulduğunuz değer köşenin değerinden azsa, ziyaret köşenin değerini güncelleyip queue a atın. Eğer ziyaret edilen köşenin değeri azsa hiçbir şey yapmayın.

 

 

Örnek:

 

Grafiğimiz şekildeki gibi olsun.

 

 

 

 

 

 

• Başlangıç noktamız A olsun. A nın değerini 0, diğer noktaların değerini sonsuz yaparak, A yi queue a atıyoruz.

 

 

 

 

 

 

 

• Queue den A yı alıp B ve C nin değerlerini güncelliyoruz. A nın yi ziyaret edilmiş olarak işaretliyoruz.

 

 

 

 

 

 

Queue den C yı alıp B, D ve E nin değerlerini güncelliyoruz. C nın yi ziyaret edilmiş olarak işaretliyoruz.

 

 

 

 

 

 

• Queue den E yi alıyoruz. E den D ye 14 ile gidebiliyoruz ama D nin değeri 11 olduğu için değiştirmiyoruz. E yi ziyaret edilmiş olarak işaretliyoruz.

 

 

 

 

 

 

 

Queue den B yı alıp D nin değerini güncelliyoruz. B nın yi ziyaret edilmiş olarak işaretliyoruz.

 

 

• 

 

 

• Queue den D yi alıp ziyaret edilmiş olarak işaretliyoruz.