Dijkstra Algoritmasi C örneği ( Iki dugum arasi mesafe hesabi)

Bu algoritmanın Türkçe anlamı ve amacı en kısa yolun bulunmasıdır.Bu ister bir ağ üzerinde veya iki 

şehir arasındaki mesafede olsun minimum mesafeyi bulmaya yarayan bir algoritmadır.Bu algoritmada
kullanılan mantık etiketleme mantığıdır.Yani bir başlangıç noktasından başlayıp sonra ayrılan yolların 
ucundaki diğer bir eleman bir düğüm sayılır ve bu düğümlere kalıcı veya geçici gibi etiketler atanır.
Geçici olması demek daha kısa bir yol bulunduğunda iptal edilebilir olması kalıcı ise en kısa yolun olmasıdır.

 #include<stdio.h>
#define MAX 10 //Maksimum düðüm sayýsý programda farklý yerlerdede kullanýlacak.
#define sonsuz 9999 // baþlangýçta düðümlere sonsuz distance deðeri verilir dijkstra algorithm.
struct dugum
{
int onceki;
int dist; /* o düðümün kaynaða olan minimum mesafesi */
int durum;
};
int adj[ MAX ][ MAX ];
int n;
void create_graph() //Graphý tanýmlayan adjacent matrixi
{
n = 5;
adj[1][2] = 4;
adj[2][1] = 4;
adj[2][3] = 3;
adj[3][2] = 3;
adj[3][4] = 4;
adj[4][3] = 4;
adj[1][4] = 8;
adj[4][1] = 8;
adj[4][5] = 7;
adj[5][4] = 7;
} /*SON*/
void display() {  //Adjancent matrixi ekrana yazdýrma
int i, j;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
printf("%3d", adj[i][j]);
printf("\n");
}
} /*SON*/
int findpath(int s, int d, int path[ MAX ], int* sdist) {
struct dugum state[ MAX ];
int i, min, count = 0, current, newdist, u, v;
*sdist = 0;
/*Tüm düðümleri geçici temp e al */
for (i = 1; i <= n; i++)
{
state[i].onceki = 0;
state[i].dist = sonsuz;
state[i].durum = 0;
}
/*Source dugum kalýcý olmalý*/
state[s].onceki = 0;
state[s].dist = 0;
state[s].durum = 1;
/*Hedef bulunana kadar kaynak düðümden baþla*/
current = s;
while (current != d)
{
for (i = 1; i <= n; i++)
{
/*geçici komþu düðümleri kontrol et */
if (adj[current][i] > 0 && state[i].durum == 0)
{
newdist = state[current].dist + adj[current][i];
/*Kontrol*/
if (newdist < state[i].dist)
{
state[i].onceki = current;
state[i].dist = newdist;
}
}
} /*SON*/
/*Geçici düðümlerde minimum mesafesi olaný ara ve current düðüm yap*/
min = sonsuz;
current = 0;
for (i = 1; i <= n; i++)
{
if (state[i].durum == 0 && state[i].dist < min)
{
min = state[i].dist;
current = i;
}
} /*son*/
if (current == 0)
return 0;
state[current].durum = 1;
} /*son*/
/* hedef ile kaynak arasý yolu arraya ata */
while (current != 0)
{
count++;
path[count] = current;
current = state[current].onceki;
}
/*kaynak ile hedef arasýndaki mesafe hesapla*/
for (i = count; i > 1; i--)
{
u = path[i];
v = path[i - 1];
*sdist += adj[u][v];
}
return (count);
} /*SON*/
void main() {
int i;
int first, second;
int path[ MAX ];
int shortdist, count;
create_graph();
printf("Adjacency matrix  :\n");
display();
while (1)
{
printf("1.Dugumu giriniz(Cikmak icin 0 a basin) : ");
scanf("%d", &first);
printf("2.Dugumu giriniz(Cikmak icin 0 a basin) : ");
scanf("%d", &second);
if (first == 0 || second == 0)
break;
count = findpath(first, second, path, &shortdist);
if (shortdist != 0)
{
printf("En kisa mesafe (maliyet) : %d\n", shortdist);
printf("En kisa yol : ");
for (i = count; i > 1; i--)
printf("%d->", path[i]);
printf("%d", path[i]);
printf("\n");
}
else
printf("Bu iki dugum arasinda yol bulunmamaktadir.\n");
}  /*SON*/
} /*Main SON*/