Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: Imagine you are a delivery driver in a city. You want to find the shortest path from your starting location to all other locations on the map. The city map is represented as a graph where intersections are nodes and roads are edges with distances.

🎯 Goal: You will build a program that uses Dijkstra's algorithm to find the shortest distance from a starting node to all other nodes in a weighted graph.

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Set a starting node for the algorithm

Implement Dijkstra's algorithm to find shortest paths

Print the shortest distances from the start node to all other nodes

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, GPS navigation, network routing, and delivery optimization.

💼 Career

Understanding Dijkstra's algorithm is essential for software engineers working with graphs, routing algorithms, and optimization problems.

1

Create the graph as an adjacency list

Create a constant called graph as a Record<string, Array<{node: string, weight: number}>> with these exact entries: 'A' connected to 'B' with weight 4 and 'C' with weight 2, 'B' connected to 'C' with weight 5 and 'D' with weight 10, 'C' connected to 'E' with weight 3, 'E' connected to 'D' with weight 4, and 'D' connected to 'F' with weight 11.

DSA Typescript

// Your code here

Hint

Use an object where keys are node names and values are arrays of objects with node and weight.

2

Set the starting node

Create a constant called startNode and set it to the string 'A'.

DSA Typescript

const graph: Record> = {
  'A': [{node: 'B', weight: 4}, {node: 'C', weight: 2}],
  'B': [{node: 'C', weight: 5}, {node: 'D', weight: 10}],
  'C': [{node: 'E', weight: 3}],
  'E': [{node: 'D', weight: 4}],
  'D': [{node: 'F', weight: 11}],
  'F': []
};

// Your code here

Hint

Just create a constant with the exact name startNode and value 'A'.

3

Implement Dijkstra's algorithm

Create a function called dijkstra that takes graph and startNode as parameters and returns a Record<string, number> of shortest distances. Use a distances object to store distances, initialize all to Infinity except startNode which is 0. Use a visited set to track visited nodes. While there are unvisited nodes, pick the unvisited node with the smallest distance, update distances to neighbors if shorter paths are found, and mark the node visited. Return the distances object.

DSA Typescript

const graph: Record> = {
  'A': [{node: 'B', weight: 4}, {node: 'C', weight: 2}],
  'B': [{node: 'C', weight: 5}, {node: 'D', weight: 10}],
  'C': [{node: 'E', weight: 3}],
  'E': [{node: 'D', weight: 4}],
  'D': [{node: 'F', weight: 11}],
  'F': []
};

const startNode = 'A';

// Your code here

Hint

Use a loop to pick the closest unvisited node, update neighbors, and mark visited until all nodes are visited.

4

Print the shortest distances

Call the dijkstra function with graph and startNode, store the result in shortestDistances, then print shortestDistances using console.log.

DSA Typescript

const graph: Record> = {
  'A': [{node: 'B', weight: 4}, {node: 'C', weight: 2}],
  'B': [{node: 'C', weight: 5}, {node: 'D', weight: 10}],
  'C': [{node: 'E', weight: 3}],
  'E': [{node: 'D', weight: 4}],
  'D': [{node: 'F', weight: 11}],
  'F': []
};

const startNode = 'A';

function dijkstra(graph: Record>, startNode: string): Record {
  const distances: Record = {};
  const visited = new Set();

  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[startNode] = 0;

  while (visited.size < Object.keys(graph).length) {
    let currentNode: string | null = null;
    let smallestDistance = Infinity;

    for (const node in distances) {
      if (!visited.has(node) && distances[node] < smallestDistance) {
        smallestDistance = distances[node];
        currentNode = node;
      }
    }

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

    for (const neighbor of graph[currentNode]) {
      const newDistance = distances[currentNode] + neighbor.weight;
      if (newDistance < distances[neighbor.node]) {
        distances[neighbor.node] = newDistance;
      }
    }

    visited.add(currentNode);
  }

  return distances;
}

// Your code here

Hint

Call the function and print the result exactly as shown.