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]

## No comments:

## Post a Comment