Pathfinding: Dijkstra’s Algorithm

One of the best known and, above all, most efficient algorithms for determining the shortest path between two points on a graph is Dijkstra’s algorithm. It is typically formulated to find the shortest path from a starting node to all other nodes in a graph, however, in this instance, a destination node will be introduced for clarity.

Attention: The algorithm fails for graphs with negative edge weights.

Process

Initial conditions

Given is a weighted graph with:

  • Node: Dot
  • Edge: Connections between nodes with a certain length/weight
  • Start and destination nodes

Every node contains three properties:

  • Distance: Sum of the distance to the start node (initially infinite)
  • Predecessor: Previous node of the shortest known path so far (initially empty)
  • Visited: Whether the node has already been processed.

Additional support structures:

  • Nodes to be visited: Queue of nodes sorted by distance in ascending order.
  • Cursor: Current node under scrutiny.

Algorithm

  1. Set the start node’s distance to 0 and add it to the queue.
  2. Pop a node from the queue (inherently the one with the lowest distance), assign it to the cursor and mark it as visited.
  3. The process may be terminated if the cursor points to the end node.
  4. For each unvisited neighbour of the cursor:
    • Calculate a new possible distance: \(d_{new} = \text{distance of the cursor} + \text{edge length}\)
      • Should the new distance (\(d_{new}\)) be smaller than the stored distance of the neighbour, assign the cursor as its predecessor, overwrite its distance with the new value and finally update the node in the queue (or add if it is not already present).
  5. Repeat step 2 until the queue is empty.
  6. The shortest route can now be travelled through each predecessors.

Example

A handy visualisation can be found at the link below.

In this tool, the graph is randomly generated, wherein nodes are called “vertexes”, visited is “known”, distance is “cost” and predecessor is “path”.

To execute the algorithm, enter the numeric id of the start vertex into the “Start Vertex” field and click “Run Dijkstra”.

Visualisation website: https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html