Skip to main content
Talentd

Minimum Distance Excluding One Maximum Weighted Edge - Solution & Explanation

MediumPremiumFree on FleetCode19 min read
Practice this problem

Problem Statement

You are given a positive integer n and a 2D integer array edges, where edges[i] = [ui, vi, wi].

There is a weighted connected simple undirected graph with n nodes labeled from 0 to n - 1. Each [ui, vi, wi] in edges represents an edge between node ui and node vi with positive weight wi.

The cost of a path is the sum of weights of the edges in the path, excluding the edge with the maximum weight. If there are multiple edges in the path with the maximum weight, only the first such edge is excluded.

Return an integer representing the minimum cost of a path going from node 0 to node n - 1.

 

Example 1:

Input: n = 5, edges = [[0,1,2],[1,2,7],[2,3,7],[3,4,4]]

Output: 13

Explanation:

There is only one path going from node 0 to node 4: 0 -> 1 -> 2 -> 3 -> 4.

The edge weights on this path are 2, 7, 7, and 4.

Excluding the first edge with maximum weight, which is 1 -> 2, the cost of this path is 2 + 7 + 4 = 13.

Example 2:

Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,50000]]

Output: 0

Explanation:

There are two paths going from node 0 to node 2:

  • 0 -> 1 -> 2

The edge weights on this path are 1 and 1.

Excluding the first edge with maximum weight, which is 0 -> 1, the cost of this path is 1.

  • 0 -> 2

The only edge weight on this path is 1.

Excluding the first edge with maximum weight, which is 0 -> 2, the cost of this path is 0.

The minimum cost is min(1, 0) = 0.

 

Constraints:

  • 2 <= n <= 5 * 104
  • n - 1 <= edges.length <= 109
  • edges[i] = [ui, vi, wi]
  • 0 <= ui < vi < n
  • [ui, vi] != [uj, vj]
  • 1 <= wi <= 5 * 104
  • The graph is connected.

Approach Overview

Problem Overview: Given a weighted graph, compute the minimum distance from source to destination where the largest edge weight on the chosen path is ignored in the final cost. If a path has total weight sum and its maximum edge weight is maxEdge, the effective distance becomes sum - maxEdge. The task is to choose a path that minimizes this adjusted distance.

Approach 1: Brute Force Edge Exclusion + Dijkstra (O(E * (V log V)) time, O(V + E) space)

Iterate over each edge and treat it as the "excluded maximum" candidate. Temporarily adjust the graph so that the selected edge does not contribute to the distance calculation, then run Dijkstra to compute the shortest path from source to destination. Track the minimum result across all candidates. This works because the excluded edge must be the largest edge on the chosen path, but the approach is expensive since shortest path computation runs for every edge.

Approach 2: Modified Dijkstra Tracking Maximum Edge (O(E log V) time, O(V) space)

Use a priority queue similar to standard Dijkstra, but each state keeps two values: the total path sum and the largest edge weight seen so far. The priority is determined by sum - maxEdge, which represents the effective cost after excluding the largest edge. When relaxing an edge, update sum and recompute maxEdge = max(currentMax, edgeWeight). Push the new state into the heap and keep the best effective distance for each node. This approach explores paths in increasing order of the adjusted cost and efficiently finds the optimal route.

The algorithm behaves like standard shortest path search but carries extra state to account for the removable maximum edge. Graphs with up to thousands of nodes remain efficient because the heap operations dominate the complexity.

Recommended for interviews: Interviewers expect the optimized modified Dijkstra solution. The brute force version shows understanding of shortest path fundamentals, but recognizing that the largest edge can be tracked during traversal demonstrates deeper knowledge of graph algorithms, Dijkstra's algorithm, and shortest path optimization. The final complexity of O(E log V) matches standard shortest path performance while handling the extra constraint.

Solution

The problem is essentially equivalent to finding a path from node 0 to node n-1, where we have one opportunity to treat the weight of a traversed edge as 0, in order to minimize the sum of path weights.

We first convert edges into an adjacency list g, where g[u] stores all edges (v, w) connected to node u, indicating that there is an edge with weight w between node u and node v.

Next, we use Dijkstra's algorithm to find the shortest path. We define a 2D array dist, where dist[u][0] represents the minimum sum of path weights from node 0 to node u without using the opportunity to treat an edge weight as 0; dist[u][1] represents the minimum sum of path weights from node 0 to node u having already used the opportunity to treat an edge weight as 0.

We use a priority queue pq to store pending nodes. Initially, we enqueue (0, 0, 0), indicating that we start from node 0, with a current path weight sum of 0, and haven't used the opportunity.

In each iteration, we dequeue the node (cur, u, used) with the minimum path weight sum from the priority queue. If the current path weight sum cur is greater than dist[u][used], we skip this node.

If the current node u is node n-1 and we have already used the opportunity used = 1, we return the current path weight sum cur.

For each edge (v, w) of node u, we calculate the path weight sum to reach node v without using the opportunity: nxt = cur + w. If nxt < dist[v][used], we update dist[v][used] and enqueue (nxt, v, used).

If we haven't used the opportunity yet used = 0, we calculate the path weight sum to reach node v when using the opportunity: nxt = cur. If nxt < dist[v][1], we update dist[v][1] and enqueue (nxt, v, 1).

After the traversal ends, we return dist[n-1][1] as the answer.

The time complexity is O(m times log n), and the space complexity is O(n + m), where n and m are the number of nodes and edges, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Edge Exclusion + DijkstraO(E * (V log V))O(V + E)Useful for understanding the problem or when the graph is very small
Modified Dijkstra Tracking Maximum EdgeO(E log V)O(V)General case and interview‑expected optimal solution

Frequently Asked Questions

Is Minimum Distance Excluding One Maximum Weighted Edge easy or hard?
This problem is typically classified as Medium difficulty. Standard Dijkstra knowledge is required, but the twist of excluding the maximum edge weight requires tracking additional state during traversal.
Minimum Distance Excluding One Maximum Weighted Edge Python/Java solution
Implement the modified Dijkstra algorithm using a priority queue. In Python, use heapq; in Java, use PriorityQueue with a custom comparator based on adjusted distance (sum minus maxEdge). The same logic works in C++, Go, TypeScript, and Rust.
How to solve Minimum Distance Excluding One Maximum Weighted Edge in O(E log V)?
Run Dijkstra while tracking two values for each path: the cumulative sum of weights and the maximum edge weight seen so far. The priority queue orders states by the adjusted distance (sum minus maxEdge). When relaxing edges, update both values and push the new state if it improves the effective cost for that node.
What is the best approach for Minimum Distance Excluding One Maximum Weighted Edge?
The most efficient approach uses a modified Dijkstra algorithm. While traversing the graph, track both the total path weight and the largest edge encountered so far. The effective cost becomes totalWeight minus maxEdge. Using a priority queue keeps the complexity at O(E log V), which is optimal for weighted graphs.
Is Minimum Distance Excluding One Maximum Weighted Edge asked at Google/Amazon/Meta?
Graph shortest‑path variations like this appear frequently in interviews at companies such as Google, Amazon, and Meta. Candidates are often expected to adapt Dijkstra's algorithm to support extra constraints like discounts, skipped edges, or modified path costs.
What data structure is used in Minimum Distance Excluding One Maximum Weighted Edge?
The core data structures are an adjacency list to store the graph and a min‑heap priority queue for Dijkstra traversal. Additional variables track the running sum and the maximum edge weight on the current path.
What is the time complexity of Minimum Distance Excluding One Maximum Weighted Edge?
The optimal solution runs in O(E log V) time using a priority queue based Dijkstra traversal. Each edge relaxation pushes a state into the heap, and heap operations dominate the runtime. Space complexity is O(V) for storing distances and state information.

Ready to solve this problem?

Practice Minimum Distance Excluding One Maximum Weighted Edge with our built-in code editor and test cases.

Practice on FleetCode