Dijkstra's Algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

Practical applications of Dijkstra's algorithmCopy Anchor Link

• GPS / navigation systems
• Public transit and airline route optimization
• Internet routing (OSPF, IS-IS protocols)
• Network traffic & latency optimization
• Game pathfinding (shortest path on maps)
• Logistics & delivery route optimization
• Supply chain & transportation network design

Step-by-step Dijkstra's algorithm exampleCopy Anchor Link

Let's say we have a weighted graph of nodes, where each edge has a distance parameter between nodes. Let's say the distance from node A and node B is 7 meters (or just 7m for brevity), and so on.

The algorithm uses Priority Queue to always pull the next unvisited vertex that has the smallest distance from the origin node.

The start node, by definition, has a distance of 0m from itself. So we start from it, the only node in the priority queue.

The rest of the nodes will be added to the priority queue later during the graph traversal (while visiting the neighbors).

Each neighbor of the pulled (from the queue) node is being traversed to calculate the distance to it from the origin. For example, the distance from A to B is 0m + 7m = 7m, and so on.

Every time we visit a not-yet-seen neighbor, we add it to the priority queue, where the priority is the distance to the neighbor node from the origin node.

The node B is being added to the min priority queue to be traversed later.

Visiting the next neighbor C of the node A. The distance from the origin node A to C is 0m + 9m = 9m.

The node C is being added to the min priority queue to be traversed later.

Same for the node F. The current distance to F from the origin node A is 0m + 14m = 14m.

The node F is being added to the min priority queue to be traversed later.

Once all the neighbors of the current node were checked, the current node was added to the visited set. We don't want to visit such nodes once again during the upcoming traverses.

Now, let's pull out the next node from the priority queue that is closest to the origin (has a shorter distance). We start visiting its neighbors as well.

If the node that we're visiting (in this case, the node C) is already in the queue, it means we already calculated the distance to it before, but from another node/path (A → C). If the current distance to it (from the current neighbor node A → B → C) is shorter than the one that was calculated before, we update the distance (in the priority queue) to the shortest one, since we're searching for the shortest paths. If the distance from the current neighbor is actually longer than the one that was already calculated, we leave it like this without updating the C node distance in the queue.

While visiting the node C via B (the path A → B → C), we see that the distance to it would be 7m + 10m = 17m. This is actually longer than the already recorded distance of 9m for the path A → C. In such cases, we just ignore the longest distance and don't update the priority (the minimum found distance at the moment from the origin node).

Visiting another neighbor of B, which is D. The distance to D equals 7m + 15m = 22m. Since we didn't visit D yet and it is not in the min priority queue, let's just add it to the queue with a priority (distance) of 22m.

At this point, all of the neighbors of B were traversed, so we add B to the visited set. Next, we pull the node that is closest to the origin node from the priority queue.

Traversing the unvisited neighbors of the node C. The distance to node F via C (the path A → C → F) is 9m + 2m = 11m. This is actually shorter than the previously recorded path A → F of 14m length. In such cases, we update the distance to F to 11m and update its priority in the queue from 14m to 11m. We've just found a shorter path to F.

The same goes for D. We've just found a shorter path to D, where A → C → D is shorter than A → B → D. Updating the distance from 22m to 20m.

All neighbors of C were traversed, so we may add C to the visited set. Pulling the next closest node from the queue, which is F.

Recording the distance to E as 11m + 9m = 20m.

Adding the node F to the visited set, and pulling the next closest node D from the queue.

Distance to E via D is 20m + 6m = 26m. This is longer than the already calculated distance to E from F, which is 20m. We can discard the longer distance.

Node D is visited now.

Node E is visited now as well. We've finished the graph traversal.

Now we know the shortest distances to each node from the start node A.

In practice, during the distance calculations, we also record the previousVertices for each node to be able to show the exact sequence of nodes that form the shortest path.

For example, the shorter path from A to E is A → C → F → E.

Implementation exampleCopy Anchor Link

• dijkstra.js

CodeCopy Anchor Link

import PriorityQueue from '../../../data-structures/priority-queue/PriorityQueue';

/**
 * @typedef {Object} ShortestPaths
 * @property {Object} distances - shortest distances to all vertices
 * @property {Object} previousVertices - shortest paths to all vertices.
 */

/**
 * Implementation of Dijkstra algorithm of finding the shortest paths to graph nodes.
 * @param {Graph} graph - graph we're going to traverse.
 * @param {GraphVertex} startVertex - traversal start vertex.
 * @return {ShortestPaths}
 */
export default function dijkstra(graph, startVertex) {
  // Init helper variables that we will need for Dijkstra algorithm.
  const distances = {};
  const visitedVertices = {};
  const previousVertices = {};
  const queue = new PriorityQueue();

  // Init all distances with infinity assuming that currently we can't reach
  // any of the vertices except the start one.
  graph.getAllVertices().forEach((vertex) => {
    distances[vertex.getKey()] = Infinity;
    previousVertices[vertex.getKey()] = null;
  });

  // We are already at the startVertex so the distance to it is zero.
  distances[startVertex.getKey()] = 0;

  // Init vertices queue.
  queue.add(startVertex, distances[startVertex.getKey()]);

  // Iterate over the priority queue of vertices until it is empty.
  while (!queue.isEmpty()) {
    // Fetch next closest vertex.
    const currentVertex = queue.poll();

    // Iterate over every unvisited neighbor of the current vertex.
    currentVertex.getNeighbors().forEach((neighbor) => {
      // Don't visit already visited vertices.
      if (!visitedVertices[neighbor.getKey()]) {
        // Update distances to every neighbor from current vertex.
        const edge = graph.findEdge(currentVertex, neighbor);

        const existingDistanceToNeighbor = distances[neighbor.getKey()];
        const distanceToNeighborFromCurrent = distances[currentVertex.getKey()] + edge.weight;

        // If we've found shorter path to the neighbor - update it.
        if (distanceToNeighborFromCurrent < existingDistanceToNeighbor) {
          distances[neighbor.getKey()] = distanceToNeighborFromCurrent;

          // Change priority of the neighbor in a queue since it might have became closer.
          if (queue.hasValue(neighbor)) {
            queue.changePriority(neighbor, distances[neighbor.getKey()]);
          }

          // Remember previous closest vertex.
          previousVertices[neighbor.getKey()] = currentVertex;
        }

        // Add neighbor to the queue for further visiting.
        if (!queue.hasValue(neighbor)) {
          queue.add(neighbor, distances[neighbor.getKey()]);
        }
      }
    });

    // Add current vertex to visited ones to avoid visiting it again later.
    visitedVertices[currentVertex.getKey()] = currentVertex;
  }

  // Return the set of shortest distances to all vertices and the set of
  // shortest paths to all vertices in a graph.
  return {
    distances,
    previousVertices,
  };
}

ReferencesCopy Anchor Link

• Wikipedia
• On YouTube by Nathaniel Fan
• On YouTube by Tushar Roy