Computer Notes, Programming codes, Hardware and Networking Tip, Entertainment, Biography, Internet Tip, Tech News, Latest Technology, YouTube,

Finding Shortest Path in Graph (Dijkstra's Algorithm)

dijkstra's algorithm, Dijkstra's shortest path algorithm, Discrete Structure, finding shortest path in graph, Graph theory, shortest path algorithm, shortest path example,



Dijkstra's algorithm is used to find the shortest path between source vertex (a) to destination vertex (b).


According to Dijkstra's algorithm, to find the shortest path from source vertex to destination vertex we need to follow the following steps.
Step 1: Remove all the loops
Step 2: Remove all parallel edges between two vertices except the one with least weight.
Step 3: Create the weight matrix table
            i) Set 0 to the source vertex and infinite to the remaining vertices.
                        For all vertices, repeat (ii) and (iii)
            ii) Mark the smallest unmarked value and mark that vertex.
            iii) Find those vertices which are directly connected with marked vertex and update all.
                  Update value formula:
                  New Destination value = Minimum(Old destination value, Marked value + Edge weight)
Step 4: Perform backtrack
Some Examples: 

1. Find shortest path from a to g. 



2. Find shortest path from a to c. 


Post a Comment

MKRdezign

Contact Form

Name

Email *

Message *

Powered by Blogger.
Javascript DisablePlease Enable Javascript To See All Widget