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 element edges[i] represents an edge in the form of [a_i, b_i, w_i]. Here, a_i and b_i are the nodes connected by the edge, and w_i is its weight.
  • Two specific nodes source and destination.
  • An integer target representing the desired shortest distance between source and destination.

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 and destination 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:

  1. Dijkstra's Algorithm Initialization: The solution defines a nested function dijkstra, which initializes a graph g with inf (infinity) values. Each edges entry with a positive weight (i.e., not -1) populates the graph g with the corresponding weight between the two nodes.

  2. Setting Up Distances and Visitations: Distances from the source to all nodes are initialized to inf, except for the source itself, which is set to 0. A vis list keeps track of which nodes have already been visited throughout the algorithm.

  3. 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.

  4. Running Dijkstra's Algorithm for Initial Graph: Before modifying any -1 weights, we run Dijkstra's algorithm to see if the target distance is already met, exceeded, or not reached given the current configuration of the graph.

  5. 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 to inf because they are not part of the shortest path and thus can be assigned any large value without affecting the result.

  6. Modifying -1 Weights: For each edge with a -1 weight, we set the weight initially to 1, 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 to target, we've found at least one -1 edge that can be part of a valid shortest path.

  7. 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.

  8. 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 cell g[a][b] holds the weight of the edge between nodes a and b.
  • dist: A list of distances from the source 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example 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 of O(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 are m such edges, the function is called m+1 times in total.
  • Assuming m is the number of edges having a weight of -1, the overall time complexity is O(m * n^2).

Space Complexity

The space complexity of the code is primarily determined by:

  • The graph g, which is an n x n matrix, thus requiring O(n^2) space.
  • The dist array, which keeps track of the shortest path from the source to each vertex, requiring O(n) space.
  • The vis array, which tracks visited vertices, also requiring O(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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄