Purpose

Dijkstra's algorithm is an efficent path finding algorithm to find the shortest weighted path between two nodes in a graph.

Example graph:

Sample Graph

requirements for algorithm

Steps

  • Pick start node
  • Add that node to itself as a path with cost 0
  • Add all possible paths starting from that node to prority queue
  • These paths have the weight of the current edge+ the total path cost
  • Repeat steps until you get terminal node
  • If this node is already visited, skip to next node
  • Return the path to this node if is terminal node