Make your own free website on Tripod.com

 

 

> ABOUT ME >RESUME >LINKS I LIKE >MAIN PAGE>GUESTBOOK

 

Implementation of Dijkstra Algorithm ( In C / C++ )

( Click on the underlined heading above to see the program code . )

Here 's the Dijkstra Algorithm for finding the Shortest Path starting from a given point :

Dijkstra-Algorithm ( Graph G ( Vertices V , Edges E ) , Starting vertex V1)

{ toBeChecked[] is an array of all the vertices

currDist[] = Array containing Current Distances

currDist[ V1 ] = 0 , all the rest are Infinite

While toBeChecked[] is not Empty

Select the Vertex u present in toBeChecked[] having minimum currDist

for all vertices v present in toBeChecked and adjacent to u

if ( currDist[v] > currDist[u] + Weight of Edge uv )

then currDist[u] = currDist[u] + Weight of Edge (uv) ,predecessor[v] = u

Remove u from toBeChecked[]

currDist[] contains the Shortest Distances

}

 

 

 

> ABOUT ME >RESUME >LINKS I LIKE >MAIN PAGE>GUESTBOOK

 

 

Home Page of Prashant Bhattacharji , Sophomore , IIT Kharagpur . Contains Resume , programs in Visual Basic , C , C++ , graphics in 2 D and 3 D .

Programs for : Eight Queens / N Queens using backtracking /recursion , heuristics . Program for Knight's Tour using Warsndorff Accessibility heuristic .