Dijkstra’s algorithm c++ coding explanation ?

[Fisher86]

hi,this code describing the work of Dijkstra’s algorithm,but i dont know how it works,anyone can explain please ?! or at least explaining the main codes meaning
int min(int n)
{
int i, result;
for(i=0;i<n;i++)
if(!(flag[i])) result=i;
for(i=0;i<n;i++)
if((l[result]>l[i])&&(!flag[i])) result=i;
return result;
}

word minim(word x, word y)
{
if(x<y) return x;
return y;
}

//алгоритм Дейкстры:
for(i=0;i<n;i++)
{
flag[i]=0;
l[i]=65535;
}
l[xn]=0;
flag[xn]=1;
p=xn;
itoa(xn+1,s,10);
for(i=1;i<=n;i++)
{
strcpy(path[i],"X");
strcat(path[i],s);
}
do
{
for(i=0;i<n;i++)
if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
{
if(l[i]>l[p]+c[p][i])
{
itoa(i+1,s,10);
strcpy(path[i+1],path[p+1]);
strcat(path[i+1],"-X");
strcat(path[i+1],s);
}
l[i]=minim(l[i],l[p]+c[p][i]);
}
p=min(n);
flag[p]=1;
}
while(p!=xk);

[mynicks]

It is difficult to read. place your code inside codetags:

{code}

your code here

{/code}

use [] instead of {}.

[Duthomhas]

Sorry, no one wants to look through that. But understanding Dijkstra's Shortest Path Algorithm may help.

The purpose is that, given a graph (directed or undirected) which is CONNECTED and has NO NEGATIVE edges, you can choose a specific vertex (we'll call it s) and then quickly compute the minimum distance paths from s to every other vertex in the graph.

This is the same kind of thing that your phone's GPS map software does for you when you ask how to get to an address from where you currently are. The nodes are intersections and the edges are roads, and the weights are either distances or time to travel (or some combination of both). The idea is to find the quickest/shortest distance to that address from your current location.

The trick is that for every intersection not yet visited, but directly connected to an already-visited intersection, you can update the total distance to it (from the source location). That means that you only need to look at each intersection once, and only consider intersections directly connected to it.

There's a lot you can google about how it works as well, including some animations.

Good luck!

(PS. If your graph does have negative weights, you'll have to use another algorithm, like the Bellman-Ford, to compute shortest paths.)

[Fisher86]

thanks for the notes