DIJKSTRA'S ALGORITHM

If you have any queries please leave a message here
Your Message
×


Consider the following network. Use Dijkstra's shortest path algorithm to compute the shortest path from the source node A to the destination node G.


1) Create a set "SPT Set" (Shortest Path Tree Set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.

2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.

3) While sptSet doesn’t include all vertices -


Start from vertex A and update distance values of its adjacent vertices which is B and C.
Initial STP Set { A }.


Pick the vertex with minimum distance value and not already included in SPT Set. The vertex C is picked and added to SPT Set.
So SPT Set now becomes { A , C }.
Update the distance values of adjacent vertices of C. The distance value of vertex D and F becomes 7 and 11 respectively.


Again pick the vertex with minimum distance value and not already included in SPT Set. The vertex B is picked and added to SPT Set.
So SPT Set now becomes { A , C , B }.
Update the distance values of adjacent vertices of B. The distance value of vertex E is 12.


Next vertex D is picked and added to SPT Set.
So SPT Set now becomes { A , C , B , D }.
There is no undiscover adjacent vertices of D.


Next vertex F is picked and added to SPT Set.
So SPT Set now becomes { A , C , B , D , F }.
Update the distance values of adjacent vertices of F. The distance value of vertex G is 15.


We repeat the above steps until SPT Set doesn’t include all vertices of given graph.


Finally, we get the following Shortest Path Tree (SPT) { A , C , B , D , F , E, G }.



ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us