# Dijkstra’s shortest path algorithm

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a* SPT (shortest path tree)* with given source as root.

Steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.

**1)** Create a set *sptSet* (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

….**a)** Pick a vertex u which is not there in *sptSet* and has minimum distance value.

….**b)** Include u to *sptSet*.

….**c)** Update distance value of all adjacent vertices of u.

*For example click below..*

#Dijkstra #Algorithm #Greedy #ShortestPathTree #Probyto #ProbytoAI

Subscribe and follow us for latest news in Data Science and Machine learning and stay updated!

Facebook: https://facebook.com/probyto

Twitter: https://twitter.com/probyto

LinkedIn: https://linkedin.com/company/probyto

Instagram: https://instagram.com/probyto