Optimal Route Calculation — Problem Statement & Solution Guide

DesignMediumDijkstra's Algorithm

TimeO(N·M)

SpaceO(N+M)

Problem Description

Given an undirected weighted graph with N vertices numbered from 1 to N and M edges, each edge connects two distinct vertices u and v and carries an integer weight w (weights may be negative but the graph contains no negative‑weight cycles). For a specified source vertex S and destination vertex T, compute the minimum possible total weight of any path that starts at S and ends at T. If no such path exists, output the word "IMPOSSIBLE". The solution must run in O((N+M) log N) when all edge weights are non‑negative and fall back to an O(N·M) approach when negative edges are present, ensuring correctness for the full range of allowed inputs.

DSA Pattern Breakdown

"Optimal Route Calculation"

medium

WHY DOES IT MATTER?

Handling negative edge weights correctly is essential because many real‑world graphs (e.g., financial transaction networks, routing with subsidies) contain such edges. A wrong algorithm can produce incorrect distances or infinite loops, leading to costly bugs in production systems.

OPTIMIZATION CHALLENGE

The key insight is that you can compute shortest paths with negative edges by repeatedly relaxing edges (Bellman–Ford) or by using a queue to process only affected vertices (SPFA). This reduces the time from exponential (exploring all paths) to linear in the number of edges, and the space to storing only distances and adjacency lists.

REAL-WORLD CONNECTION

Consider a logistics network where certain routes offer rebates (negative costs). A routing engine must still compute the cheapest overall path, even if some legs reduce the total cost. Ignoring negative edges would miss optimal routes and could result in higher shipping costs.

When interviewing, emphasize early termination: once the target vertex’s distance is finalized (i.e., it is popped from the priority queue in Dijkstra or no longer improves in Bellman–Ford), you can break out of the loop, saving time on large graphs.

COMPLEXITY AT A GLANCE

⏱ Time:O(N·M)

💾 Space:O(N+M)

Core Theory — Why This Approach?

The problem asks for the shortest path in an undirected weighted graph that may contain negative edge weights but is guaranteed to have no negative‑weight cycles. A naive breadth‑first search or simple DFS that explores all paths would explode combinatorially, leading to exponential time and memory usage. The optimal paradigm is to use a relaxation‑based algorithm that guarantees convergence in a linear number of passes over the edges. Bellman–Ford relaxes all edges N-1 times, guaranteeing the shortest distances even with negative weights, while SPFA (a queue‑based variant) often performs better in practice by only re‑processing vertices whose distances improve. For a single source–destination query, these algorithms run in O(N·M) time and O(N+M) space, which is tractable for graphs up to several hundred thousand edges.

Because the graph is undirected, each edge appears twice in the adjacency list, but the relaxation logic remains the same. The absence of negative cycles means that after N-1 relaxations the distances are final; any further improvement would indicate a cycle. Thus, the algorithm can terminate early once the target vertex’s distance is finalized, saving unnecessary work.

In many interview settings, candidates will attempt to use Dijkstra’s algorithm, which fails when negative weights are present. The key insight is that re‑weighting edges to eliminate negatives (Johnson’s algorithm) is overkill for a single query; instead, a straightforward Bellman–Ford or SPFA suffices and demonstrates mastery of graph relaxation techniques.

Interview Questions on This Problem

Q1How would you modify Dijkstra’s algorithm to handle negative edge weights in a graph that has no negative cycles?

You cannot directly modify Dijkstra because it relies on the non‑negative weight property to guarantee that once a vertex is popped from the priority queue its distance is final. The correct approach is to use a relaxation‑based algorithm such as Bellman–Ford or SPFA, which repeatedly relax edges regardless of sign. If you must use Dijkstra, you can first run a Bellman–Ford from a dummy source to compute potentials, re‑weight all edges to be non‑negative, then run Dijkstra on the re‑weighted graph and finally adjust the distances back.

Q2In a fintech routing system, why is it important to detect negative cycles, and how would you do it efficiently?

Negative cycles represent arbitrage opportunities or data inconsistencies that could lead to infinite profit loops or routing errors. To detect them efficiently, run Bellman–Ford for N iterations; if any distance improves on the Nth iteration, a negative cycle exists. Alternatively, use the SPFA algorithm with a counter for each vertex’s relaxation count; if a vertex is relaxed more than N times, a negative cycle is present.

Q3What is the time complexity of the SPFA algorithm in the worst case, and how does it compare to Bellman–Ford for sparse graphs?

In the worst case, SPFA can degrade to O(N·M), just like Bellman–Ford, especially on graphs with many negative edges. However, for sparse graphs with mostly positive edges, SPFA typically runs in near‑linear time because each vertex is enqueued only a few times. Thus, SPFA is often preferred in practice for single‑source shortest path queries when negative weights are present but negative cycles are absent.

Examples

Example 1

Input

Output

Explanation: All possible S‑T paths are examined. The path 1→2 (weight 2), 2→3 (weight -1) and 3→5 (weight 3) yields a total weight of 2 + (-1) + 3 = 4, which is smaller than the direct path 1→3→5 (4 + 3 = 7) or any route involving vertex 4. Hence the shortest distance from 1 to 5 is 4.

Example 2

Input

Output

Explanation: The graph contains a single simple chain 1‑2‑3‑4. Adding the edge weights gives 5 + 6 + (-2) = 9. No alternative edges exist, so the unique path is also the shortest. The answer is 9.

Example 3

Input

3 1
1 2 3
1 3

Output

IMPOSSIBLE

Explanation: Vertex 3 is isolated from the component containing vertices 1 and 2. Consequently there is no path from the source 1 to the target 3, and the required output is the string "IMPOSSIBLE".

Constraints

1 <= N <= 100000
0 <= M <= 200000
-1000000 <= w <= 1000000
1 <= S, T <= N
The graph does not contain any cycle whose total weight is negative.

Optimal Approach & Strategy

Use Bellman–Ford or SPFA to relax all edges N-1 times, updating distances even for negative weights. This guarantees the shortest path in O(N·M) time and O(N+M) space.

Brute Force Approach

Enumerate all simple paths from S to T, compute their total weights, and return the minimum. This approach has exponential time complexity and is infeasible for large graphs.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N·M)

function bellmanFord(graph, start) {
   const distance = {};
   for (const node in graph) {
       distance[node] = Infinity;
   }
   distance[start] = 0;
   for (let i = 0; i < Object.keys(graph).length - 1; i++) {
       for (const node in graph) {
           for (const neighbor in graph[node]) {
               const weight = graph[node][neighbor];
               if (distance[node] + weight < distance[neighbor]) {
                   distance[neighbor] = distance[node] + weight;
               }
           }
       }
   }
   return distance;
}

int* bellmanFord(int** graph, int start, int size) {
   int* distance = new int[size];
   for (int i = 0; i < size; i++) {
       distance[i] = INT_MAX;
   }
   distance[start] = 0;
   for (int i = 0; i < size - 1; i++) {
       for (int node = 0; node < size; node++) {
           for (int neighbor = 0; neighbor < graph[node][0]; neighbor++) {
               int weight = graph[node][neighbor + 1];
               if (distance[node] + weight < distance[neighbor]) {
                   distance[neighbor] = distance[node] + weight;
               }
           }
       }
   }
   return distance;
}

public int[] bellmanFord(int[][] graph, int start) {
   int[] distance = new int[graph.length];
   for (int i = 0; i < graph.length; i++) {
       distance[i] = Integer.MAX_VALUE;
   }
   distance[start] = 0;
   for (int i = 0; i < graph.length - 1; i++) {
       for (int node = 0; node < graph.length; node++) {
           for (int neighbor = 0; neighbor < graph[node].length; neighbor++) {
               int weight = graph[node][neighbor];
               if (distance[node] + weight < distance[neighbor]) {
                   distance[neighbor] = distance[node] + weight;
               }
           }
       }
   }
   return distance;
}

def bellman_ford(graph, start):
   distance = {node: float('inf') for node in graph}
   distance[start] = 0
   for _ in range(len(graph) - 1):
       for node in graph:
           for neighbor in graph[node]:
               weight = graph[node][neighbor]
               distance[neighbor] = min(distance[neighbor], distance[node] + weight)
   return distance

function bellmanFord(graph, start) {
   const distance = {};
   for (const node in graph) {
       distance[node] = Infinity;
   }
   distance[start] = 0;
   for (let i = 0; i < Object.keys(graph).length - 1; i++) {
       for (const node in graph) {
           for (const neighbor in graph[node]) {
               const weight = graph[node][neighbor];
               if (distance[node] + weight < distance[neighbor]) {
                   distance[neighbor] = distance[node] + weight;
               }
           }
       }
   }
   return distance;
}

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.

Optimal Route Calculation Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Design

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Optimal Route Calculation — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor