Dijkstra's Algorithm (AS)

Dijkstra’s Algorithm (AS)

Understanding Dijkstra’s Algorithm

  • Dijkstra’s Algorithm is a procedure used to find the shortest paths from a single source vertex to all other vertices in a weighted graph.
  • The algorithm starts with a source node, then iteratively updates the shortest distance to all other nodes in the graph.
  • It utilises a priority queue to select nodes for updating, choosing at each step the node with the smallest current distance from the source.
  • Dijkstra’s algorithm can only be applied to graphs with non-negative weights.

Steps of Dijkstra’s algorithm

  • Initialize all node’s distance values to infinity, except for the source node which is set to 0.
  • Set the source node as current, then update the distances to its immediate neighbours.
  • Choose the unvisited node with the smallest distance and make that node the new current node.
  • Repeat the previous two steps until all nodes have been visited.

Applications of Dijkstra’s Algorithm

  • Used extensively in network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and Open Shortest Path First (OSPF).
  • Calculation of shortest paths in transport networks, for example as part of the Google Maps route planning feature.
  • In physiology, Dijkstra’s algorithm is used in the digital image processing of CT-scans and MRI-scans to track nerve fibres in the brain.
  • This algorithm is also used in robot movement. Robots use the algorithm to find the most efficient path to go from point A to B.

##_EOF