Dijkstra’s Algorithm

  1. We have to create a set which keeps the record of all the vertices that are included in the shortest paths. Initially this set would be empty.
  2. The source vertex is assigned a distance of 0 while all other vertices are assigned distance values as infinite.
  3. Till all vertices aren’t included in the set we created in step 1, we have to repeat the following steps — Select the vertex which is not yet included in the set but has the minimum distance. — Include that vertex in the set. — Update the distance of the vertex as explained below.
  1. We have to create a min heap of size equal to the number of vertices. We have to assign each node of the min heap the vertex number and the distance of that vertex.
  2. Same as above algorithm. Source vertex is assigned 0 while rest are assigned infinite value.
  3. Till the main heap is emptied, the following steps are done — The vertex with minimum distance is taken out from min heap. — For every adjacent vertices update the distances (same as explained above).
  • It is used in finding the shortest paths of graphs
  • In social networking applications, it is used for suggesting “friends” or to derive important relations from the community graph of the social network.
  • It is used in telephone networks.
  • To find the locations on the map. The minimum distance from one location to another.
  • It is used in designing of train, subway networks. Where the shortest path from one city to another needs to be routed.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Maharaj Mahaadev

Maharaj Mahaadev

I'm a Computer Science engineering Student who loves gaming.