Dijkstra's Algorithm

Introduction

Dijkstra's algorithm is a fundamental graph algorithm used to find the shortest path between nodes in a weighted graph. Named after its creator, Dutch computer scientist Edsger W. Dijkstra, this algorithm has applications in various fields, including routing in computer networks, transportation, and more.

Basics of Dijkstra's Algorithm

Algorithm Overview

Dijkstra's algorithm operates on a graph, which consists of nodes (vertices) and edges (connections between nodes). It finds the shortest path from a designated starting node (the source) to all other nodes in the graph. Here are the basic steps:

• 1. Initialize a distance table: Create a data structure to store the shortest known distance from the source to each node. Initially, set the distance to the source node as 0 and the distance to all other nodes as infinity.
• 2. Select the unvisited node with the smallest distance in the distance table.
• 3. Update distances: For the selected node, consider all of its unvisited neighbors. Calculate their tentative distances through the current node and compare them with the existing recorded distances. If a shorter path is found, update thedistance table.
• 4. Mark the selected node as visited.
• 5. Repeat steps 2-4 until all nodes have been visited.
• 6. Backtrack to find the shortest path: After visiting all nodes, you can backtrack from the destination node to the source node to determine the shortest path.

Data Structures

• Distance Table: This data structure stores the shortest known distances from the source node to all other nodes. It is often implemented as an array or dictionary, where each node is associated with its current distance value.
• Priority Queue: To efficiently select the unvisited node with the smallest distance, a priority queue is used. This data structure ensures that nodes with shorter distances are selected first.
• Path Map (Previous Nodes): In Dijkstra's algorithm, a data structure known as a Map<Vertex, Vertex> is commonly used to store information about the previous node for each node in the shortest path. In this map, each node (Vertex) is associated with its previous node on the shortest path. If there is no previous node (e.g., for the source node or disconnected nodes), it is represented as null or not included in the map.

Code example of the Algorithm

import { Graph, Vertex, Edge } from './yourGraphLibrary'; // Import necessary graph-related classes/interfaces

public async dijkstra(
  graph: Graph,
  sourceVertex: Vertex
): Promise<{ distances: Map<Vertex, number>; previous: Map<Vertex, Vertex | null> }> {
  const distances: Map<Vertex, number> = new Map();
  const unvisited: Set<Vertex> = new Set(graph.getVertices());
  const previous: Map<Vertex, Vertex | null> = new Map();

  // Initialize distances
  for (const vertex of graph.getVertices()) {
    distances.set(vertex, Infinity);
    previous.set(vertex, null);
  }
  distances.set(sourceVertex, 0);

  while (unvisited.size !== 0) {
    let currentVertex: Vertex | null = null;
    let smallestDistance = Infinity;

    // Find the unvisited vertex with the smallest distance
    unvisited.forEach((vertex) => {
      const dist = distances.get(vertex) ?? Infinity;
      if (dist < smallestDistance) {
        smallestDistance = dist;
        currentVertex = vertex;
      }
    });

    if (currentVertex === null) {
      break;
    }

    unvisited.delete(currentVertex);

    // Get neighbors of the current vertex
    const neighbors = graph.getAdjacentVertices(currentVertex);
    for (const neighbor of neighbors) {
      if (unvisited.has(neighbor)) {
        // Get edges between the current vertex and its neighbor
        const edges = graph.getEdgesFromVertices(currentVertex, neighbor);

        // Find the minimum-weight edge
        const minEdge: Edge = edges.reduce((prev, curr) =>
          prev.Weight < curr.Weight ? prev : curr
        );

        // Calculate the new distance to the neighbor
        const alt = distances.get(currentVertex) + minEdge.Weight!;

        // If the new distance is shorter, update the distances and previous nodes
        if (alt < distances.get(neighbor)) {
          distances.set(neighbor, alt);
          previous.set(neighbor, currentVertex);
        }
      }
    }
  }

  return { distances, previous };
}

Playground - Visualization