Minimum Weighted Path Distance — Problem Statement & Solution Guide
Problem Description
Consider a directed weighted graph with N vertices labeled 0 through N-1. The graph is defined by an adjacency list edges, where each element is a triplet [u, v, w] indicating a directed edge from node u to node v with a non-negative integer weight w. Given a source node src and a destination node dst, determine the minimum cumulative weight required to traverse a path from src to dst. If no such path exists, return -1.
The input consists of the integer N, the list of edges, the integer src, and the integer dst. The output is a single integer representing the shortest path distance or -1 if unreachable. All edge weights are non-negative, ensuring that standard shortest-path algorithms applicable to non-negative weights can be utilized.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Weighted Path Distance"
WHY DOES IT MATTER?
Shortest‑path problems appear in routing, logistics, and network latency optimization; mastering Dijkstra’s algorithm equips engineers to design efficient, cost‑aware systems that scale to millions of nodes.
OPTIMIZATION CHALLENGE
The key insight is the greedy selection of the next vertex with the smallest tentative distance using a min‑heap, which ensures each vertex is processed exactly once and each edge is relaxed at most once, collapsing exponential possibilities into near‑linear time.
REAL-WORLD CONNECTION
Think of a GPS navigation system: each road segment is an edge with travel time as weight, and the device must quickly compute the fastest route from the current location (src) to the destination (dst) without exploring every possible road combination.
In an interview, start by stating the problem as a single‑source shortest‑path with non‑negative weights, then immediately propose Dijkstra with a priority queue; if the candidate mentions a binary heap, be ready to discuss alternatives like a Fibonacci heap for O(E + V log V) time.
COMPLEXITY AT A GLANCE
O((V + E) log V)O(V + E)Core Theory — Why This Approach?
The problem of finding the minimum cumulative weight from a source to a destination in a directed weighted graph with non‑negative edge weights is a classic single‑source shortest‑path problem. The naive approach of enumerating all possible paths quickly becomes infeasible because the number of simple paths can grow exponentially with the number of vertices, leading to exponential time and memory consumption. Dijkstra’s algorithm leverages a greedy strategy combined with a min‑priority queue to always expand the currently known closest vertex, guaranteeing that once a vertex is extracted from the queue its shortest distance is final. This optimal paradigm runs in O((V+E) log V) time with a binary heap, making it suitable for large sparse graphs typical in real‑world applications.
When edge weights are non‑negative, the greedy choice property holds: the shortest path to a vertex cannot be improved by later exploring longer paths. This property eliminates the need for backtracking or exhaustive search, allowing the algorithm to relax edges only once per vertex extraction. In contrast, algorithms like Bellman‑Ford, which handle negative weights, incur O(VE) time, and BFS (which assumes unit weights) fails to respect varying costs. Thus, Dijkstra’s algorithm is the optimal solution for this problem domain, balancing correctness with efficiency.
Interview Questions on This Problem
Q1How would you modify Dijkstra’s algorithm to also return the actual path (list of vertices) from src to dst?
Maintain a predecessor array (or map) that records the vertex from which each node’s distance was last relaxed. After the algorithm finishes, backtrack from dst using this array to reconstruct the path in reverse order.
Q2If the graph could contain zero‑weight cycles, does Dijkstra’s algorithm still work? Why or why not?
Yes, Dijkstra’s algorithm remains correct with zero‑weight cycles because the greedy property only requires non‑negative weights; zero does not create a situation where a later discovered path could improve an already settled vertex’s distance.
Q3Explain how you would adapt the solution for a massive graph that cannot fit entirely in memory, such as a road network stored on disk.
Use a variant of Dijkstra’s algorithm with a disk‑based priority queue (e.g., external memory heap) and process the graph in chunks, loading adjacency lists on demand. Techniques like A* with an admissible heuristic or hierarchical routing (Contraction Hierarchies) further reduce I/O by pruning irrelevant nodes.
Examples
Input
N = 4, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1]], src = 0, dst = 3
Output
4
Explanation: Starting at node 0, there are two immediate options: go to node 1 with weight 4, or go to node 2 with weight 1. Taking the path 0 -> 2 (cost 1) and then 2 -> 1 (cost 2) results in a cumulative cost of 3 to reach node 1. From node 1, the edge to node 3 has weight 1. The total cost for the path 0 -> 2 -> 1 -> 3 is 1 + 2 + 1 = 4. The direct path 0 -> 1 -> 3 would cost 4 + 1 = 5. Thus, the minimum distance is 4.
Input
N = 3, edges = [[0,1,5],[1,2,5]], src = 0, dst = 2
Output
10
Explanation: The only path from node 0 to node 2 is 0 -> 1 -> 2. The weight of edge 0->1 is 5, and the weight of edge 1->2 is 5. The sum is 5 + 5 = 10.
Input
N = 5, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,10]], src = 0, dst = 4
Output
4
Explanation: There is a direct edge from 0 to 4 with weight 10. However, there is also a path 0 -> 1 -> 2 -> 3 -> 4. The weights are 1, 1, 1, and 1 respectively. The sum is 1 + 1 + 1 + 1 = 4. Since 4 < 10, the minimum distance is 4.
Input
N = 2, edges = [[0,1,7]], src = 1, dst = 0
Output
-1
Explanation: The graph contains an edge from 0 to 1, but no edge from 1 to 0. Since the graph is directed, there is no path from source 1 to destination 0. Therefore, the result is -1.
Constraints
- 1 <= N <= 10^4
- 0 <= M <= 10^4
- 0 <= src, dst < N
- 0 <= w <= 10^4
- The graph may contain multiple edges between the same pair of nodes.
Optimal Approach & Strategy
Apply Dijkstra’s algorithm with a priority queue to greedily expand the closest vertex and relax edges, guaranteeing the shortest distance in O((V+E) log V) time.
Brute Force Approach
Enumerate every possible path from src to dst using DFS or BFS, compute each path’s total weight, and keep the minimum; this is exponential in the worst case.
Verified Code Solutions
function minimumWeightedPathDistance(graph, src, dst) {
const n = graph.length;
const distance = new Array(n).fill(Infinity);
distance[src] = 0;
const queue = [src];
while (queue.length > 0) {
const node = queue.shift();
for (let i = 0; i < n; i++) {
if (graph[node][i] !== 0 && distance[node] + graph[node][i] < distance[i]) {
distance[i] = distance[node] + graph[node][i];
queue.push(i);
}
}
}
return distance[dst] === Infinity ? -1 : distance[dst];
}class Solution {
public:
int minimumWeightedPathDistance(vector<vector<int>>& graph, int src, int dst) {
int n = graph.size();
vector<int> distance(n, INT_MAX);
distance[src] = 0;
queue<int> q;
q.push(src);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int i = 0; i < n; i++) {
if (graph[node][i] != 0 && distance[node] + graph[node][i] < distance[i]) {
distance[i] = distance[node] + graph[node][i];
q.push(i);
}
}
}
return distance[dst] == INT_MAX ? -1 : distance[dst];
}
}class Solution {
public int minimumWeightedPathDistance(int[][] graph, int src, int dst) {
int n = graph.length;
int[] distance = new int[n];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[src] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(src);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int i = 0; i < n; i++) {
if (graph[node][i] != 0 && distance[node] + graph[node][i] < distance[i]) {
distance[i] = distance[node] + graph[node][i];
queue.add(i);
}
}
}
return distance[dst] == Integer.MAX_VALUE ? -1 : distance[dst];
}
}def minimum_weighted_path_distance(graph, src, dst):
n = len(graph)
distance = [float('inf')] * n
distance[src] = 0
queue = [src]
while queue:
node = queue.pop(0)
for i in range(n):
if graph[node][i] != 0 and distance[node] + graph[node][i] < distance[i]:
distance[i] = distance[node] + graph[node][i]
queue.append(i)
return -1 if distance[dst] == float('inf') else distance[dst]function minimumWeightedPathDistance(graph, src, dst) {
const n = graph.length;
const distance = new Array(n).fill(Infinity);
distance[src] = 0;
const queue = [src];
while (queue.length > 0) {
const node = queue.shift();
for (let i = 0; i < n; i++) {
if (graph[node][i] !== 0 && distance[node] + graph[node][i] < distance[i]) {
distance[i] = distance[node] + graph[node][i];
queue.push(i);
}
}
}
return distance[dst] === Infinity ? -1 : distance[dst];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.