Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.
Ans:
The Dijkstra's algorithm: This is a problem which is concerned with finding the least cost path from an originating node in a weighted graph to a destination node in that particular graph.
The Dijkstra's algorithm is stated below:
Let G=(V,E) be the simple graph. Let a and z be any two vertices on the graph. Let L(x ) denotes the label of the vertex x which represent the length of shortest path from the vertex a to the vertex x and wij which denotes the weight of the edge eij=
1. Let P=φ where P is the set of those vertices which
Are having permanent labels and T={all vertices in graph}
|
|
Set L(a)=0,
|
L(x)=∞ for all x≠a
|
|
|
2.
|
Select the
label. This
|
vertex v in T which has
label is called permanent
|
the smallest
label of v.
|
Also set P=P {v} and T=T-{v}
If v=z then L(z) is the length of the shortest path from the vertex a to z and stop.
3. If v is not equal to z then revise the labels of vertices of T that is the vertices which do not consist of permanent labels.
The new label of vertex x in T can be given by
L(x)=min(old L(x), L(v)+w(v, x))
Here w(v, x) is the weight of the edge joining the vertex v and x. If there exists no direct edge joining v and x then take w(v, x)= ∞
4. Repeat steps 2 and 3 until get the permanent z label.