Dijkstra Algoritması, C Örneği

Dijkstra Algoritması iki nokta arasında en iyi rotayı bulmada önemli algoritmalardan biridir. Diyelim ki aşağıdaki şekilde A'dan E'ye en iyi rotayı bulmaya çalışıyoruz. Gördüğümüz kadarıyla A'dan E'ye toplam 6 yolla gidilebilir (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE) ve açıkça görülüyor ki en ideal yol ABDE. Çünkü toplam ağırlığı (uzunluk diyebiliriz) en azı o. Ancak gerçek hayatta her zaman bunun gibi kolayca görülebilen örneklerle karşılaşmayız. Daha karmaşık problemleri algoritmalar tarafından çözebiliriz.

1- Aşağıdaki şekilde görüldüğü gibi  kaynak nodu (A) geçici nodu (şu an üzerinde bulunduğumuz nod) olarak seçilmiş. Bu yüzden seçilenler grubuna dahil edilebilir (Secilenler grubuna dahil edilenleri içi mavi renkle dolu yuvarlaklar şeklinde göstereceğiz). 

2- Bu aşamada gidilecek iki alternatif var (B ve C). B'nin ağırlığı C'den daha az olduğu için şimdi B'yi seçiyoruz ve onu geçici nod atayıp seçilenler grubuna ekliyoruz.
3-  Şimdi, 2. aşamadaki gibi gidilebilecek alternatiflerden (D ve E) ağırlığı en az olanını yani D'yi geçici nod seçelim ve seçilenler grubuna dahil edelim.
4-  Buradan da E'ye 1 ağırlıklı DE yolunu kullanarak gidilir.
5- E'ye yani hedef nodumuza ulaştık, burada duralım.
 

E'ye ulaştığımıza göre artık rotayı belirleyebiliriz. Tersten giderek (E-D...) rotayı ABDE şeklinde buluruz. Toplam ağırlık da 1+2+1 = 4'tür.

Bu algoritma sorunsuz çalışmasına rağmen router'ların bunu işlemesi uzun süre alabilir ve ağın verimliliği başarısız olabilir. Özellikle de eğer bir router diğerlerine yanlış bilgi verirse tüm bu rota kararları verimsizleşebilir. Algoritmayı daha iyi anlamak için C'de yazılmış kaynak koduna bir göz atalım:

#define MAX_NODES 1024 /* maksimum nod sayısı */
#define INFINITY 1000000000 /* olabilecek en buyuk sayı */
int n,dist[MAX_NODES][MAX_NODES]; /*dist[I][j], i'den j'ye uzaklığı verir */
void shortest_path(int s,int t,int path[ ])
{

struct state { /* üzerinde uğraştığımız yol */
int predecessor ; /*önceki nod */
int length /*kaynaktan bu noda olan uzunluk*/
enum {permanent, tentative} label /*label'in şu anki durumu (kalıcı mı geçici mi)*/
}state[MAX_NODES];
int I, k, min;
struct state *
p;
for (p=&state[0];p < &state[n];p++){ /*durumları ilk duruma al*/
p->predecessor=-1
p->length=INFINITY
p->label=tentative;
}
state[t].length=0; state[t].label=permanent ;
k=t ; /*k, ilk ele alacağımız nod */
do{ /* k'dan daha iyi bir yol var mı? */
for I=0; I < n; I++) /*bu graf'ın n nodu var */
if (dist[k][I] !=0 && state[I].label==tentative){
if (state[k].length+dist[k][I] < state[I].length){
state[I].predecessor=k;
state[I].length=state[k].length + dist[k][I]
}
}
/* Geçici etiketli olanlardan en kısa yola sahip olanı bul. */
k=0;min=INFINITY;
for (I=0;I < n;I++){
if(state[I].label==tentative && state[I].length < min)=state[I].length;
k=I;
}
state[k].label=permanent;
}while (k!=s);
/*Bu yolu çıktıya kopyala*/
I=0;k=0
Do{
path[I++]=k;k=state[k].predecessor;
} while (k > =0);
}



kaynak: www.gevisgetiren.com

Yorum Yaz