Skip to content

Dijkstras Shortest Path Algorithm

Intuition

Given:

  • you have some nodes
  • some edges which have some weight assigned to them
  • and you have one node for which we have to find
  • shortest path to all other edges

Setup:

  • you create two arrays
    • array which contain the shortest distance to that node
    • and the source node through which you will reach this node, this help in reconstruction of path

Algorithm:

  • Create a set
  • assign all the elements the distance \(+\infty\) except source node which is \(0\)
  • now repeat these steps till all nodes are not in the set
    • choose the node with smallest distance and which is not in the set
    • add that to the set
    • now check for all adjacent nodes of the picked node
      • if path through node is smaller or not
      • \(d(a, b) = \min(d(a, c) + d(c, b))\)
      • if yes update distance and source to this node
  • now you have shortest distance