2699. Modify Graph Edge Weights
Problem Description
In this problem, you are presented with an undirected, weighted, connected graph consisting of n
nodes, where each edge connects two nodes and has an associated weight. The input for the problem includes:
- The number of nodes
n
. - An integer array
edges
, where each elementedges[i]
represents an edge in the form of[a_i, b_i, w_i]
. Here,a_i
andb_i
are the nodes connected by the edge, andw_i
is its weight. - Two specific nodes
source
anddestination
. - An integer
target
representing the desired shortest distance betweensource
anddestination
.
The weights of some edges are -1
, indicating that you need to assign them a new, valid positive integer weight. Other edges have positive integer weights that must not be changed. Your goal is to assign positive integer weights to all edges with weight -1
such that the shortest distance between the source
and destination
nodes is exactly equal to target
. The new weights should be within the range [1, 2 * 10^9]
.
If you can find one or more ways to modify the weights of -1
edges to achieve the target distance, you should return the edges array with modifications. If there is no way to make the modifications such that the shortest distance becomes equal to the target, you should return an empty array. The problem stipulates that there may be multiple valid modifications that satisfy the requirement, and any correct modification gets accepted.
Intuition
The intuition behind the solution relies on Dijkstra's algorithm for finding the shortest paths between nodes in a graph with non-negative edge weights. The algorithm is modified to accommodate the fact that some weights must be decided during execution.
Initially, the algorithm runs with the original graph, ignoring edges with weights set to -1
and treating them as non-existent. This initial run determines whether the target shortest distance is already met, exceeded, or not reached.
- If the current shortest distance between
source
anddestination
is less than the target, the task is impossible, so we return an empty array. There's no possible way to increase the weight of the edges to make the shortest path exactly equal to the target. - If the shortest distance is exactly equal to the target, then all
-1
edges can be assigned any large positive weight without affecting the current shortest path. We do this as the shortest path does not include these-1
edges. - If the current shortest path exceeds the target, there is a possibility of adjusting the weights of
-1
edges to reduce the overall path distance to match the target.
The edges with -1
weight are then traversed one by one. If the target has been met, these edges are assigned a very large weight, not interfering with the previously calculated paths. If the target has not been met, they are assigned a weight of 1
. After each edge assignment, Dijkstra's algorithm runs again to check if the new weight configuration results in the desired target distance. If the current shortest path is smaller or equal to the target while modifying a -1
edge, this edge is updated with the required additional weight to elevate the path distance to exactly match the target.
In summary, the solution iteratively attempts to adjust the weights of -1
edges while monitoring the effect of each assignment on the shortest path between source
and destination
. Through constant verification with Dijkstra's algorithm, the solution ensures that each edge weight is adjusted properly to achieve the target distance while fulfilling the constraints.
Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.
Solution Approach
The solution approach involves a few key steps and the use of Dijkstra's algorithm to find the shortest path in the graph:
-
Dijkstra's Algorithm Initialization: The solution defines a nested function
dijkstra
, which initializes a graphg
withinf
(infinity) values. Eachedges
entry with a positive weight (i.e., not-1
) populates the graphg
with the corresponding weight between the two nodes. -
Setting Up Distances and Visitations: Distances from the
source
to all nodes are initialized toinf
, except for thesource
itself, which is set to0
. Avis
list keeps track of which nodes have already been visited throughout the algorithm. -
Finding the Shortest Path: The core of Dijkstra's algorithm loops through the nodes, finds the unvisited node with the smallest distance, marks it as visited, and updates the distances to its neighbors. If a shorter path to a neighbor is found, it gets updated with the new minimum distance.
-
Running Dijkstra's Algorithm for Initial Graph: Before modifying any
-1
weights, we run Dijkstra's algorithm to see if thetarget
distance is already met, exceeded, or not reached given the current configuration of the graph. -
Handling Different Scenarios:
-
If the initial shortest distance is less than
target
, it's impossible to adjust the weights since we can't decrease the distances by increasing the weights. Hence, an empty array is returned. -
If the initial shortest distance is exactly
target
, then all-1
weights are set toinf
because they are not part of the shortest path and thus can be assigned any large value without affecting the result.
-
-
Modifying
-1
Weights: For each edge with a-1
weight, we set the weight initially to1
, then run Dijkstra's algorithm again to determine the new shortest path. If the modified graph now has a shortest path that is less than or equal totarget
, we've found at least one-1
edge that can be part of a valid shortest path. -
Adjusting Weights to Match Target: If adjusting an edge made the path too short, we increase the weight of that specific edge by the difference between the target and the new shortest path, so the shortest distance now equals
target
. -
Returning the Result: The updated edges array is returned if it's possible to adjust the
-1
edges to achieve the target distance; otherwise, an empty array is returned if the task is impossible.
The main data structures used here are:
g
: A 2D list representing the graph where each cellg[a][b]
holds the weight of the edge between nodesa
andb
.dist
: A list of distances from thesource
node to all other nodes in the graph.vis
: A list that keeps track of which nodes have been visited.
The pattern used is a known greedy algorithm pattern, as Dijkstra's algorithm makes the optimal choice at each step as it works towards the final solution. The modification of -1
edge weights adds a layer of complexity as the algorithm seeks not just the shortest path but also an adjustment of unspecified weights to meet a target path length.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have a graph with 4 nodes, and we're given the following edges
input to illustrate the solution approach:
1n = 4 2edges = [[1, 2, 2], [2, 3, -1], [3, 4, 3], [1, 4, 6]] 3source = 1 4destination = 4 5target = 8
This configuration of edges represents an undirected graph where nodes are connected as such: Node 1 to Node 2 with a weight of 2, Node 2 to Node 3 with an unspecified weight (-1
), Node 3 to Node 4 with a weight of 3, and Node 1 to Node 4 with a weight of 6.
Step 1: Dijkstra's Algorithm Initialization
Our graph initially ignores the edge with the -1
weight, so it looks like this:
- Node 1 to Node 2: 2
- Node 1 to Node 4: 6
- Node 3 to Node 4: 3
The graph data structure g
is prepared, with inf
representing non-existent edges.
Step 2: Setting Up Distances and Visitations
Distances are initialized to inf
, with the source node distance set to 0
. In our example:
- dist[1] = 0
- dist[2] = inf
- dist[3] = inf
- dist[4] = inf
A vis
list is also initialized to keep track of visited nodes.
Step 3: Finding the Shortest Path without Edge [2, 3] We apply Dijkstra's algorithm to find the shortest paths from the source to all nodes. For simplicity, we find:
- The shortest path from Node 1 to Node 4 is through the direct edge [1, 4] with a weight of 6, which is not the target distance (8).
Step 4: Running Dijkstra's Algorithm for Initial Graph
We initially ignore the edge [2, 3] with a -1
weight and find the shortest path to the destination with existing edges only.
Step 5: Handling Different Scenarios Since 6 (the initial shortest distance) is less than 8 (the target), we need to consider modifying the weight of the edge [2, 3] as it might help us meet the target distance.
Step 6: Modifying -1
Weights
We'll initially set the weight of the edge [2, 3] to 1 and rerun Dijkstra's algorithm. This gives us a new path: 1 → 2 → 3 → 4, with total weight 2 + 1 + 3 = 6, which is still not enough to meet the target.
Step 7: Adjusting Weights to Match Target Now we know that the shortest path using the edge [2, 3] is 6, which is 2 less than the target distance of 8. So we need to adjust the weight of edge [2, 3] by adding 2. Therefore, this edge is updated to have a weight of 1 + 2 = 3.
Step 8: Returning the Result After our weight adjustments, we now have:
- Edge [1, 2]: weight 2
- Edge [2, 3]: weight 3 (adjusted from -1)
- Edge [3, 4]: weight 3
- Edge [1, 4]: weight 6
The shortest path from Node 1 to Node 4 now via edges [1, 2], [2, 3], and [3, 4] sums up to the target distance: 2 + 3 + 3 = 8.
Thus, the edges
array with modifications would be returned as:
1[[1, 2, 2], [2, 3, 3], [3, 4, 3], [1, 4, 6]]
If at any point we realized that we cannot meet the target distance, we would return an empty array, but in this example, our modifications have led us to successfully meet the specified target distance.
Solution Implementation
1from typing import List
2from math import inf
3
4class Solution:
5 def modifiedGraphEdges(
6 self, n: int, edges: List[List[int]], source: int, destination: int, target: int
7 ) -> List[List[int]]:
8
9 # Function to perform Dijkstra's algorithm for finding the shortest path
10 def dijkstra(edges: List[List[int]]) -> int:
11 # Create a graph initialized with 'infinity' for all distances
12 graph = [[inf] * n for _ in range(n)]
13 for start, end, weight in edges:
14 if weight == -1:
15 continue
16 graph[start][end] = graph[end][start] = weight
17
18 # Initialize distances from source to all nodes as 'infinity', except for the source itself
19 distances = [inf] * n
20 distances[source] = 0
21 visited = [False] * n # Keeps track of visited nodes
22
23 # Perform the algorithm
24 for _ in range(n):
25 nearest_unvisited_node = -1
26
27 # Select the nearest unvisited node
28 for j in range(n):
29 if not visited[j] and (nearest_unvisited_node == -1 or distances[nearest_unvisited_node] > distances[j]):
30 nearest_unvisited_node = j
31
32 # Mark the selected node as visited
33 visited[nearest_unvisited_node] = True
34
35 # Update the distances to other nodes using the selected node
36 for j in range(n):
37 distances[j] = min(distances[j], distances[nearest_unvisited_node] + graph[nearest_unvisited_node][j])
38
39 # Return the distance to the destination
40 return distances[destination]
41
42 # Perform the Dijkstra's algorithm with the initial graph
43 shortest_distance = dijkstra(edges)
44
45 # If the initially found distance is less than the target, return an empty list (no modifications needed)
46 if shortest_distance < target:
47 return []
48
49 # If the distance is exactly equal to the target, flag it as 'ok'
50 shortest_distance_ok = shortest_distance == target
51
52 # Iterate through the edges for possible modifications
53 for edge in edges:
54 if edge[2] > 0: # Skip edges that already have a weight greater than 0
55 continue
56
57 # If the current distance is exactly equal to the target, set the weight to infinity
58 if shortest_distance_ok:
59 edge[2] = inf
60 continue
61
62 # Try setting the edge weight to 1 and recalculate the shortest distance
63 edge[2] = 1
64 shortest_distance = dijkstra(edges)
65
66 # If the modified graph has a distance lesser than or equal to the target, update the edge weight
67 if shortest_distance <= target:
68 shortest_distance_ok = True
69 edge[2] += target - shortest_distance
70
71 # Return the modified edges if a valid modification was found, else return an empty list
72 return edges if shortest_distance_ok else []
73
1import java.util.Arrays; // Import necessary for Arrays.fill and other array operations
2
3class Solution {
4 // Use a large number to represent infinity for comparison purposes
5 private static final int INFINITY = 2000000000;
6
7 // Method to modify graph edges based on the provided conditions
8 public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
9 // First run dijkstra to find the current shortest path distance
10 long dist = dijkstra(edges, n, source, destination);
11
12 // Check if the current distance is less than the target
13 if (dist < target) {
14 return new int[0][];
15 }
16
17 // Flag to indicate if the target distance has been met or surpassed
18 boolean targetMet = dist == target;
19
20 // Iterate through each edge to adjust weights
21 for (int[] edge : edges) {
22 if (edge[2] > 0) { // Skip if the weight is already positive
23 continue;
24 }
25 if (targetMet) { // If the target distance has been met, set weight to INFINITY
26 edge[2] = INFINITY;
27 continue;
28 }
29 // Set edge weight to 1 and re-run dijkstra
30 edge[2] = 1;
31 dist = dijkstra(edges, n, source, destination);
32
33 // Check if the updated distance meets or exceeds the target
34 if (dist <= target) {
35 targetMet = true; // Update the flag
36 // Increase the weight to set the distance exactly to target
37 edge[2] += target - dist;
38 }
39 }
40
41 // Return the edges array if the target distance has been met, otherwise empty array
42 return targetMet ? edges : new int[0][];
43 }
44
45 // Dijkstra algorithm to find the shortest path in a graph
46 private long dijkstra(int[][] edges, int n, int src, int dest) {
47 int[][] graph = new int[n][n]; // Representation of graph as adjacency matrix
48 long[] distances = new long[n]; // Distances array to store minimum distance to each vertex
49 Arrays.fill(distances, INFINITY); // Initialize distances with infinity
50 distances[src] = 0; // Distance to source is 0
51
52 // Initialize graph with INFINITY weights
53 for (int[] row : graph) {
54 Arrays.fill(row, INFINITY);
55 }
56
57 // Fill in edges with weights into graph matrix
58 for (int[] edge : edges) {
59 int from = edge[0];
60 int to = edge[1];
61 int weight = edge[2];
62 if (weight == -1) continue; // Skip edges with weight -1
63 graph[from][to] = weight; // Undirected graph: use same weight for both directions
64 graph[to][from] = weight;
65 }
66
67 boolean[] visited = new boolean[n]; // Track visited vertices
68
69 // Dijkstra's algorithm implementation to update distances
70 for (int i = 0; i < n; ++i) {
71 int closestVertex = -1;
72 // Find the unvisited vertex with the smallest distance
73 for (int j = 0; j < n; ++j) {
74 if (!visited[j] && (closestVertex == -1 || distances[closestVertex] > distances[j])) {
75 closestVertex = j;
76 }
77 }
78 // Mark the closest vertex as visited
79 visited[closestVertex] = true;
80 // Update distances to all unvisited vertices if a shorter path is found
81 for (int j = 0; j < n; ++j) {
82 distances[j] = Math.min(distances[j], distances[closestVertex] + graph[closestVertex][j]);
83 }
84 }
85 // Return the distance to the destination vertex
86 return distances[dest];
87 }
88}
89
1#include <vector>
2#include <algorithm>
3#include <limits>
4
5using std::vector;
6using std::fill;
7using std::min;
8
9constexpr int INF = 2e9; // Define constant for infinity value.
10
11class Solution {
12public:
13 // Function to modify graph edges such that the shortest path equals the target distance.
14 vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
15 long long shortestDistance = dijkstra(edges, n, source, destination);
16 if (shortestDistance < target) { // If current shortest path is less than target, it's not possible.
17 return {};
18 }
19 bool isEqualToTarget = shortestDistance == target;
20 for (auto& edge : edges) {
21 if (edge[2] > 0) { // If an edge already has positive weight, skip it.
22 continue;
23 }
24 if (isEqualToTarget) { // If current path length equals target, set the weight to infinity.
25 edge[2] = INF;
26 continue;
27 }
28 // Temporarily set weight to 1 and recalculate shortest path.
29 edge[2] = 1;
30 shortestDistance = dijkstra(edges, n, source, destination);
31 if (shortestDistance <= target) { // If path matches or is smaller than target, adjust weight.
32 isEqualToTarget = true;
33 edge[2] += target - shortestDistance;
34 }
35 }
36 return isEqualToTarget ? edges : vector<vector<int>>{};
37 }
38
39 // Dijkstra's algorithm to find the shortest path from src to dest.
40 long long dijkstra(const vector<vector<int>>& edges, int n, int src, int dest) {
41 long long graph[n][n];
42 long long distance[n];
43 bool visited[n];
44
45 // Initialize all distances to INF and visited to false.
46 for (int i = 0; i < n; ++i) {
47 fill(graph[i], graph[i] + n, INF);
48 distance[i] = INF;
49 visited[i] = false;
50 }
51 distance[src] = 0; // Distance to source is 0.
52
53 // Initialize graph with edges that have non-negative weight.
54 for (const auto& edge : edges) {
55 int from = edge[0], to = edge[1], weight = edge[2];
56 if (weight == -1) {
57 continue;
58 }
59 graph[from][to] = weight;
60 graph[to][from] = weight;
61 }
62
63 // Applying Dijkstra's algorithm.
64 for (int i = 0; i < n; ++i) {
65 int closestUnvisitedNode = -1;
66 for (int j = 0; j < n; ++j) {
67 if (!visited[j] && (closestUnvisitedNode == -1 || distance[j] < distance[closestUnvisitedNode])) {
68 closestUnvisitedNode = j;
69 }
70 }
71 visited[closestUnvisitedNode] = true;
72 for (int j = 0; j < n; ++j) {
73 distance[j] = min(distance[j], distance[closestUnvisitedNode] + graph[closestUnvisitedNode][j]);
74 }
75 }
76
77 // Return the shortest distance to the destination.
78 return distance[dest];
79 }
80};
81
1function modifiedGraphEdges(
2 nodeCount: number,
3 edges: number[][],
4 sourceNode: number,
5 destNode: number,
6 targetDistance: number,
7): number[][] {
8 // Initialize a very large value as a placeholder for infinity
9 const INF = 2e9;
10
11 // Dijkstra's algorithm implementation to find the shortest path
12 const dijkstra = (edges: number[][]): number => {
13 // Graph representation with distances initialized to infinity
14 const graph: number[][] = Array(nodeCount)
15 .fill(0)
16 .map(() => Array(nodeCount).fill(INF));
17 // Array to hold shortest distances from source
18 const dist: number[] = Array(nodeCount).fill(INF);
19 // Boolean array to track visited nodes
20 const visited: boolean[] = Array(nodeCount).fill(false);
21
22 // Convert adjacency list to adjacency matrix and skip edges with weight -1
23 for (const [from, to, weight] of edges) {
24 if (weight === -1) {
25 continue;
26 }
27 graph[from][to] = weight;
28 graph[to][from] = weight;
29 }
30
31 // Distance from source to itself is always 0
32 dist[sourceNode] = 0;
33
34 // Find the shortest path to each node
35 for (let i = 0; i < nodeCount; ++i) {
36 let closestNode = -1;
37 for (let j = 0; j < nodeCount; ++j) {
38 if (!visited[j] && (closestNode === -1 || dist[j] < dist[closestNode])) {
39 closestNode = j;
40 }
41 }
42 visited[closestNode] = true;
43
44 // Update the distances for the neighbors of the closestNode
45 for (let neighbor = 0; neighbor < nodeCount; ++neighbor) {
46 dist[neighbor] = Math.min(dist[neighbor], dist[closestNode] + graph[closestNode][neighbor]);
47 }
48 }
49
50 // Return the shortest distance to the destination node
51 return dist[destNode];
52 };
53
54 // Find the initial shortest path from source to destination
55 let shortestDistance = dijkstra(edges);
56
57 // If shortest distance is already less than target, return empty array
58 if (shortestDistance < targetDistance) {
59 return [];
60 }
61
62 // Check if the initial shortest path equals the target distance
63 let pathFound = shortestDistance === targetDistance;
64
65 // Iterate over edges to adjust weights to try meeting the target distance
66 for (const edge of edges) {
67 // Skip edges with positive weight
68 if (edge[2] > 0) {
69 continue;
70 }
71
72 // If path is already found, set edge weight to infinity to exclude it
73 if (pathFound) {
74 edge[2] = INF;
75 continue;
76 }
77
78 // Set temporary weight to 1 and recalculate shortest path
79 edge[2] = 1;
80 shortestDistance = dijkstra(edges);
81
82 // If new path meets or is lower than target, set edge weight to make the path exact
83 if (shortestDistance <= targetDistance) {
84 pathFound = true;
85 edge[2] += targetDistance - shortestDistance;
86 }
87 }
88
89 // Return the modified edges if path found, otherwise empty array
90 return pathFound ? edges : [];
91}
92
Time and Space Complexity
The provided Python code implements a modified version of the Dijkstra's algorithm to determine the shortest path in a graph and makes adjustments to the graph's edges to meet a target distance. Here is the complexity analysis:
Time Complexity
The time complexity of Dijkstra's algorithm with an adjacency matrix (without using a min-priority queue) is O(n^2)
, where n
is the number of nodes in the graph. This comes from the two nested loops: one to find the vertex with the minimum distance that has not been visited and the other to update the distances from that vertex.
In the code:
- The
dijkstra(edges)
function has a time complexity ofO(n^2)
as explained above, and it is called multiple times. - It is called once initially and then once for each edge that has a weight of
-1
(i.e., missing from the initial graph). If there arem
such edges, the function is calledm+1
times in total. - Assuming
m
is the number of edges having a weight of-1
, the overall time complexity isO(m * n^2)
.
Space Complexity
The space complexity of the code is primarily determined by:
- The graph
g
, which is ann x n
matrix, thus requiringO(n^2)
space. - The
dist
array, which keeps track of the shortest path from the source to each vertex, requiringO(n)
space. - The
vis
array, which tracks visited vertices, also requiringO(n)
space.
Since the n x n
matrix dominates, the overall space complexity is O(n^2)
for storing the graph representation.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.