Dijkstra’s Algorithm

Aim: To create a program to find the shortest path in a given graph using Dijkstra’s Algorithm.

Algorithm :

function Dijkstra(Graph, source):
for each vertex v in Graph:
dist[v] := infinity
previous[v] := undefined
dist[source] := 0
Q := the set of all nodes in Graph
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break
remove u from Q
for each neighbor v of u:
alt := dist[u] + dist_between(u, v)
if alt < dist[v]:
dist[v] := alt
previous[v] := u
return previous[]