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.

Practice

1. What is the main advantage of using topological order to find the shortest path in a Directed Acyclic Graph (DAG)?

easy

A. It finds the longest path instead of the shortest.

B. It guarantees the graph has cycles.

C. It allows processing vertices in a linear order without revisiting nodes.

D. It sorts vertices based on their weights.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that all edges go from earlier to later vertices, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order means each vertex is processed after all its predecessors, so shortest paths can be updated without revisiting.

3. Final Answer:

   It allows processing vertices in a linear order without revisiting nodes. -> Option C

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once in DAG [OK]

Common Mistakes:

• Thinking topological order applies to graphs with cycles
• Confusing shortest path with longest path
• Assuming topological order sorts by weights

2. Which TypeScript code snippet correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices?

easy

A. const dist: number[] = Array(5).fill(Infinity); dist[0] = 0;

B. const dist: number[] = new Array(5).fill(0); dist[0] = Infinity;

C. const dist: number[] = Array(5).fill(-1); dist[0] = 0;

D. const dist: number[] = new Array(5).fill(null); dist[0] = 0;

Solution

1. Step 1: Initialize distances with Infinity except source

   Distances start as Infinity to represent unknown paths; source vertex distance is 0.

2. Step 2: Check code correctness

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; uses Array(5).fill(Infinity) and sets dist[0] = 0, which is correct initialization.

3. Final Answer:

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; -> Option A

4. Quick Check:

   Distance array initialized with Infinity except source 0 [OK]

Hint: Use Infinity for unknown distances, zero for source [OK]

Common Mistakes:

• Filling distances with 0 instead of Infinity
• Setting source distance to Infinity
• Using null or -1 which are invalid for distances

3. Given the following DAG edges with weights:
edges = [[0,1,2],[0,2,4],[1,2,1],[1,3,7],[2,4,3],[3,4,1]]
and source vertex 0, what is the shortest distance array after running shortest path using topological order?

medium

A. [0, 4, 5, 8, 9]

B. [0, 2, 4, 7, 8]

C. [0, 2, 3, 7, 6]

D. [0, 2, 3, 9, 6]

Solution

1. Step 1: Calculate shortest distances step-by-step

   Start dist = [0,∞,∞,∞,∞]. From 0: dist[1]=2, dist[2]=4. From 1: dist[2]=min(4,2+1=3)=3, dist[3]=2+7=9. From 2: dist[4]=3+3=6. From 3: dist[4]=min(6,9+1=10)=6.

2. Step 2: Final shortest distances

   Distances are [0, 2, 3, 9, 6]. But check [0, 2, 3, 7, 6] has dist[3]=7, so re-check: From 1 to 3 is 7, so dist[3]=2+7=9. [0, 2, 3, 7, 6] shows 7, so [0, 2, 3, 9, 6] matches 9 for dist[3]. So [0, 2, 3, 9, 6] is correct.

3. Final Answer:

   [0, 2, 3, 9, 6] -> Option D

4. Quick Check:

   Shortest distances = [0, 2, 3, 9, 6] [OK]

Hint: Relax edges in topological order to update distances [OK]

Common Mistakes:

• Not updating distances with minimum values
• Mixing up edge weights during relaxation
• Ignoring topological order in updates

4. Identify the bug in this TypeScript code snippet for shortest path in DAG:

const dist = Array(n).fill(Infinity);
dist[0] = 0;
for (const u of topoOrder) {
  for (const [v, w] of graph[u]) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

Assuming graph is adjacency list and topoOrder is correct topological order.

medium

A. No bug; the code correctly updates shortest distances.

B. The inner loop should iterate over graph[v] instead of graph[u].

C. dist[u] should be checked for Infinity before relaxation.

D. dist array should be initialized with zeros instead of Infinity.

Solution

1. Step 1: Analyze the relaxation in topological order

   In topological order, when processing u, dist[u] has been finalized as the shortest path from source if reachable. For unreachable u, dist[u] remains Infinity.

2. Step 2: Verify Infinity handling

   In JavaScript/TypeScript, Infinity + w = Infinity for any finite w, and Infinity < dist[v] is false, so no incorrect updates occur. Thus, no explicit check is needed.

3. Final Answer:

   No bug; the code correctly updates shortest distances. -> Option A

4. Quick Check:

   Infinity + w doesn't update distances wrongly [OK]

Hint: Infinity arithmetic handles unreachable nodes [OK]

Common Mistakes:

• Thinking explicit Infinity check is required
• Iterating over wrong adjacency list
• Initializing dist with zeros

5. You have a DAG with vertices 0 to 5 and edges:
[[0,1,3],[0,2,6],[1,2,4],[1,3,4],[2,4,8],[3,4,2],[4,5,1]]
Using shortest path with topological order from source 0, what is the shortest distance to vertex 5?

hard

A. 12

B. 10

C. 11

D. 9

Solution

1. Step 1: Initialize distances and process edges

   Start dist = [0,∞,∞,∞,∞,∞]. From 0: dist[1]=3, dist[2]=6. From 1: dist[2]=min(6,3+4=7)=6, dist[3]=3+4=7. From 2: dist[4]=6+8=14. From 3: dist[4]=min(14,7+2=9)=9. From 4: dist[5]=9+1=10.

2. Step 2: Verify shortest distance to vertex 5

   Shortest distance to 5 is 10, but check if any shorter path exists: 0->1->3->4->5 = 3+4+2+1=10, 0->2->4->5=6+8+1=15. So 10 is shortest.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Shortest distance to 5 = 10 [OK]

Hint: Relax edges in topological order to find shortest path [OK]

Common Mistakes:

• Choosing longer path distances
• Ignoring better paths through intermediate vertices
• Miscomputing sums of edge weights