Shortest Path in DAG Using Topological Order in DSA Typescript - Build from Scratch

Shortest Path in DAG Using Topological Order

📖 Scenario: You are working on a project to find the shortest travel time between cities connected by one-way roads. The roads form a network without any loops, so the map is a Directed Acyclic Graph (DAG). You want to find the quickest route from the starting city to all other cities.

🎯 Goal: Build a TypeScript program that finds the shortest path distances from a starting city to all other cities in a DAG using topological order.

📋 What You'll Learn

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

Create a variable for the number of cities

Implement topological sorting using DFS

Calculate shortest paths using the topological order

Print the shortest distances array

💡 Why This Matters

🌍 Real World

Finding shortest paths in a DAG is useful in project scheduling, task ordering, and routing where cycles do not exist.

💼 Career

Understanding shortest path algorithms and topological sorting is important for software engineers working on compilers, network routing, and dependency resolution.

1

Create the graph as an adjacency list

Create a variable called graph as an adjacency list representing the following directed edges with weights:
0 -> 1 (5), 0 -> 2 (3), 1 -> 3 (6), 1 -> 2 (2), 2 -> 4 (4), 2 -> 5 (2), 2 -> 3 (7), 3 -> 4 (-1), 4 -> 5 (-2).
Use an array of arrays where each inner array contains tuples of [neighbor, weight].

DSA Typescript

# Your code here

Hint

Represent the graph as an array where each index is a city and contains a list of pairs [neighbor, weight].

2

Create the number of cities variable

Create a variable called numCities and set it to the number of cities in the graph.

DSA Typescript

const graph: Array> = [
  [[1, 5], [2, 3]],
  [[3, 6], [2, 2]],
  [[4, 4], [5, 2], [3, 7]],
  [[4, -1]],
  [[5, -2]],
  []
];
# Your code here

Hint

Use the length property of the graph array to get the number of cities.

3

Implement topological sort and shortest path calculation

Write a function called topologicalSort that takes graph and numCities and returns an array with the topological order of the cities. Then create a function called shortestPathDAG that takes graph, numCities, and a starting city start, and returns an array of shortest distances from start to all cities using the topological order. Use Infinity for unreachable cities.

DSA Typescript

const graph: Array> = [
  [[1, 5], [2, 3]],
  [[3, 6], [2, 2]],
  [[4, 4], [5, 2], [3, 7]],
  [[4, -1]],
  [[5, -2]],
  []
];
const numCities = graph.length;

// Your code here

Hint

Use DFS to get topological order. Then relax edges in that order to find shortest paths.

4

Print the shortest distances from city 1

Call the function shortestPathDAG with graph, numCities, and starting city 1. Then print the returned array of shortest distances.

DSA Typescript

const graph: Array> = [
  [[1, 5], [2, 3]],
  [[3, 6], [2, 2]],
  [[4, 4], [5, 2], [3, 7]],
  [[4, -1]],
  [[5, -2]],
  []
];
const numCities = graph.length;

function topologicalSort(graph: Array>, numCities: number): number[] {
  const visited = new Array(numCities).fill(false);
  const stack: number[] = [];

  function dfs(city: number) {
    visited[city] = true;
    for (const [neighbor] of graph[city]) {
      if (!visited[neighbor]) {
        dfs(neighbor);
      }
    }
    stack.push(city);
  }

  for (let city = 0; city >, numCities: number, start: number): number[] {
  const order = topologicalSort(graph, numCities);
  const dist = new Array(numCities).fill(Infinity);
  dist[start] = 0;

  for (const city of order) {
    if (dist[city] !== Infinity) {
      for (const [neighbor, weight] of graph[city]) {
        if (dist[city] + weight < dist[neighbor]) {
          dist[neighbor] = dist[city] + weight;
        }
      }
    }
  }

  return dist;
}

// Your code here

Hint

Call shortestPathDAG with start city 1 and print the result array.