#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);
|