Shortest Path in DAG Using Topological Order in DSA Javascript - 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 Directed Acyclic Graph (DAG), meaning there are no loops. You want to use a smart method that processes cities in an order so that when you calculate the shortest path to a city, you have already calculated the shortest paths to all cities that lead to it.

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

📋 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 from the start city 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 route planning where cycles do not exist.

💼 Career

Understanding topological sorting and shortest path algorithms is important for software engineers working on optimization, graph problems, and dependency resolution.

1

Create the graph as an adjacency list

Create a variable called graph as an array of arrays representing the adjacency list for 6 cities (0 to 5). Use these exact edges with weights: from city 0 to 1 with weight 5, from 0 to 2 with weight 3, from 1 to 3 with weight 6, from 1 to 2 with weight 2, from 2 to 4 with weight 4, from 2 to 5 with weight 2, from 2 to 3 with weight 7, from 3 to 4 with weight -1, from 4 to 5 with weight -2.

DSA Javascript

// Create the graph adjacency list with exact edges and weights
// Your code here

Hint

Use an array where each element is a list of pairs [neighbor, weight]. Follow the exact edges and weights given.

2

Set the number of cities and create a visited array

Create a variable called numCities and set it to 6. Then create a variable called visited as an array of length numCities filled with false.

DSA Javascript

const graph = [
  [[1, 5], [2, 3]],
  [[3, 6], [2, 2]],
  [[4, 4], [5, 2], [3, 7]],
  [[4, -1]],
  [[5, -2]],
  []
];

// Create numCities and visited array
// Your code here

Hint

Use new Array(numCities).fill(false) to create the visited array.

3

Implement topological sort and shortest path calculation

Write a function called topologicalSort that takes a city node and performs DFS to fill an array stack with cities in topological order. Then create a variable distances as an array of length numCities filled with Infinity. Set distances[0] to 0 as the start city. Use the stack to relax edges and update distances with shortest paths.

DSA Javascript

const graph = [
  [[1, 5], [2, 3]],
  [[3, 6], [2, 2]],
  [[4, 4], [5, 2], [3, 7]],
  [[4, -1]],
  [[5, -2]],
  []
];

const numCities = 6;
const visited = new Array(numCities).fill(false);

const stack = [];

// Write topologicalSort function and calculate shortest paths
// Your code here

Hint

Use DFS to fill stack in topological order. Then pop from stack to relax edges and update distances.

4

Print the shortest distances array

Write a console.log statement to print the distances array.

DSA Javascript

const graph = [
  [[1, 5], [2, 3]],
  [[3, 6], [2, 2]],
  [[4, 4], [5, 2], [3, 7]],
  [[4, -1]],
  [[5, -2]],
  []
];

const numCities = 6;
const visited = new Array(numCities).fill(false);

const stack = [];

function topologicalSort(node) {
  visited[node] = true;
  for (const [neighbor] of graph[node]) {
    if (!visited[neighbor]) {
      topologicalSort(neighbor);
    }
  }
  stack.push(node);
}

for (let i = 0; i < numCities; i++) {
  if (!visited[i]) {
    topologicalSort(i);
  }
}

const distances = new Array(numCities).fill(Infinity);
distances[0] = 0;

while (stack.length) {
  const node = stack.pop();
  if (distances[node] !== Infinity) {
    for (const [neighbor, weight] of graph[node]) {
      if (distances[node] + weight < distances[neighbor]) {
        distances[neighbor] = distances[node] + weight;
      }
    }
  }
}

// Print the distances array
// Your code here

Hint

Use console.log(distances) to print the final shortest distances 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 allows processing nodes in a linear order without revisiting them.

B. It guarantees the graph has cycles.

C. It sorts nodes based on their weights.

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

Solution

1. Step 1: Understand topological order in DAG

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

2. Step 2: Use topological order for shortest path

   Processing nodes in this order means each node is visited once, and distances can be updated efficiently without revisiting.

3. Final Answer:

   It allows processing nodes in a linear order without revisiting them. -> Option A

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once for shortest path [OK]

Common Mistakes:

• Thinking topological order sorts by weights
• Assuming DAG has cycles
• Confusing shortest path with longest path

2. Which of the following JavaScript code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 nodes, starting from node 0?

easy

A. const dist = Array(5).fill(-1); dist[0] = 0;

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

C. const dist = Array(5).fill(null); dist[0] = 0;

D. const dist = Array(5).fill(Infinity); dist[0] = 0;

Solution

1. Step 1: Initialize distances for shortest path

   Distances to all nodes except start should be Infinity to represent unknown paths.

2. Step 2: Set start node distance to zero

   Distance to start node (0) is zero because it is the source.

3. Final Answer:

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

4. Quick Check:

   Start distance 0, others Infinity [OK]

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

Common Mistakes:

• Setting start node distance to Infinity
• Using 0 for all distances initially
• Using null or -1 which are invalid for distances

3. Consider the following DAG represented as adjacency list with weights:

const graph = {
  0: [[1, 2], [2, 4]],
  1: [[2, 1], [3, 7]],
  2: [[4, 3]],
  3: [[4, 1]],
  4: []
};

If we run shortest path from node 0 using topological order, what is the shortest distance to node 4?

medium

A. 6

B. 7

C. 10

D. 9

Solution

1. Step 1: Find topological order and initialize distances

   Topological order could be [0,1,2,3,4]. Initialize dist = [0, Infinity, Infinity, Infinity, Infinity].

2. Step 2: Relax edges in topological order

   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.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest distance to node 4 = 6 [OK]

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

Common Mistakes:

• Not updating dist[2] to smaller value 3
• Ignoring edge from 3 to 4
• Adding weights incorrectly

4. The following code attempts to find the shortest path in a DAG using topological order but has a bug:

function shortestPath(graph, start) {
  const dist = Array(Object.keys(graph).length).fill(Infinity);
  dist[start] = 0;
  const topoOrder = topologicalSort(graph);
  for (const node of topoOrder) {
    for (const [neighbor, weight] of graph[node]) {
      if (dist[node] + weight < dist[neighbor]) {
        dist[neighbor] = dist[node] + weight;
      }
    }
  }
  return dist;
}

What is the likely cause of incorrect results?

medium

A. The start node distance is not set to zero

B. dist array is initialized with zeros instead of Infinity

C. topologicalSort function might return nodes in wrong order

D. The graph edges are not weighted

Solution

1. Step 1: Check initialization and start distance

   dist is correctly initialized with Infinity and start node distance set to 0.

2. Step 2: Verify topological order correctness

   If topologicalSort returns nodes in wrong order, relaxation will fail and distances won't update correctly.

3. Final Answer:

   topologicalSort function might return nodes in wrong order -> Option C

4. Quick Check:

   Correct topological order needed for shortest path [OK]

Hint: Ensure topological order is correct before relaxing edges [OK]

Common Mistakes:

• Assuming dist initialization is wrong
• Ignoring importance of topological order
• Forgetting to set start node distance

5. Given a DAG with nodes 0 to 5 and edges with weights:

0 -> 1 (3), 0 -> 2 (2), 1 -> 3 (4), 2 -> 3 (1), 3 -> 4 (2), 4 -> 5 (1)

If you want to find the shortest path from node 0 to node 5 using topological order, which sequence of distances will you get before processing node 3?

hard

A. [0, 3, 2, 5, Infinity, Infinity]

B. [0, 3, 2, 3, Infinity, Infinity]

C. [0, 3, 2, 3, 2, Infinity]

D. [0, 3, 2, 1, Infinity, Infinity]

Solution

1. Step 1: Initialize distances and process nodes 0,1,2

   Start dist = [0, Infinity, Infinity, Infinity, Infinity, Infinity]. After 0: dist[1]=3, dist[2]=2. After 1: dist[3]=3+4=7. After 2: dist[3]=min(7,2+1=3)=3.

2. Step 2: Before processing node 3

   At this point, node 3's distance has been finalized by its predecessors to 3, but outgoing edges from 3 have not been relaxed yet, so dist[4] and dist[5] remain Infinity. Distances: [0, 3, 2, 3, Infinity, Infinity].

3. Final Answer:

   [0, 3, 2, 3, Infinity, Infinity] -> Option B

4. Quick Check:

   Distances before relaxing node 3 edges [OK]

Hint: Check distances before relaxing edges from current node [OK]

Common Mistakes:

• Updating distances of neighbors too early
• Confusing order of relaxation
• Miscomputing minimum distances