Dijkstra's Algorithm

Hi,

I'm revamping my algo skills and thought of putting up the code in my blog for fun and for other's reference.

Following is the Dijkstra's Algorithm, which is used to find the shortest path to all nodes of a graph from a single selected node.

[code language="cpp"]

//Dijkstra's Algorithm
//Shortest Path Algo

#include
using namespace std;
#define INF 999
#define SIZE 5
bool isMoreToVisit(bool VisitedArray[5])
{
for(int i=0;i<SIZE;i++)
if(VisitedArray[i]==false) return true;
return false;
}

int main()
{
int StartNode=0;
int Distances[SIZE]={INF};
bool Visited[SIZE]={false};
int Graph[SIZE][SIZE]={{0,10,5,15,INF},{INF,0,INF,INF,INF},{INF,6,0,INF,500},{INF,INF,INF,0,8},{3,INF,INF,INF,0}};
int CurrentNode=StartNode,CurrentTrace=0;

Distances[StartNode] =0;
while(isMoreToVisit(Visited)==true)
{
Visited[CurrentNode] = true;
for(int i=0;i<SIZE;i++)
if(Visited[i]==false) //Recalib all unvisited nodes
if(Graph[CurrentNode][i]+CurrentTrace<Distances[i])
Distances[i] = Graph[CurrentNode][i]+CurrentTrace;

//Fix next node to be visited
int MinNodeVal= INF;
for(int i=0;i<SIZE;i++)
if(Visited[i]==false)
if(Distances[i]<MinNodeVal)
{
MinNodeVal= Distances[i];
CurrentNode=i;
}
CurrentTrace=MinNodeVal;
};

cout<<endl<<"Resulting answer: \n\n";
for(int j=0;j<SIZE;j++) cout<<" - "<<Distances[j];
return 0;
}
[/code]