## Tuesday, 12 February 2013

### Implementation of Dijkstra’s Shortest Path Algorithm in C++

The algorithm (Pseudo Code) is as follows

procedure Dijkstra (G): weighted connected simple graph,
with all weights positive)
[G has vertices a = v0, v1, ..... , vn = z and weights w(v1, v2)
where w(vi, vj) = INFINITY if [vi, vj] is not an edge in G]

for i := 1 to n
L(vi) := INFINITY
L(a) := 0
S := NULL
[ the labels are now initialized so that the label of a is 0
and all other labels are INFINITY, S is empty set]
while z is not belongs to S
begin
u := a vertex not in S with L(u) minimal
S := S U [u]
for all vertices u not in S
If L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v)
[this adds a vertex to S with minimal label and updates the labels
vertices no in S]
end [L(z) = length of a shortest path from a to z]

Example:

Now lets come to an example which further illustrates above algorithm. Consider a weighted graph

Here a, b, c .. are nodes of the graph and the number between nodes are weights (distances) of the graph. Now we are going to find the shortest path between source (a) and remaining vertices. The adjacency matrix of the graph is

Now the following source code implements the above example
Now the following source code implements the above example