This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
2699. Modify Graph Edge Weights
Difficulty: Hard
Topics: Graph, Heap (Priority Queue), Shortest Path
You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi.
Some edges have a weight of -1 (wi = -1), while others have a positive weight (wi > 0).
Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 109] so that the shortest distance between the nodes source and destination becomes equal to an integer target. If there are multiple modifications that make the shortest distance between source and destination equal to target, any of them will be considered correct.
Return an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from source to destination equal to target, or an empty array if it's impossible.
Note: You are not allowed to modify the weights of edges with initial positive weights.
Example 1:
- Input: n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
- Output: [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
- Explanation: The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.
Example 2:
- Input: n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
- Output: []
- Explanation: The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned.
Example 3:
- Input: n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
- Output: [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
- Explanation: The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.
Constraints:
1 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= ai, bi < n-
wi = -1or1 <= wi <= 107 ai != bi0 <= source, destination < nsource != destination1 <= target <= 109- The graph is connected, and there are no self-loops or repeated edges
Hint:
- Firstly, check that it’s actually possible to make the shortest path from source to destination equal to the target.
- If the shortest path from source to destination without the edges to be modified, is less than the target, then it is not possible.
- If the shortest path from source to destination including the edges to be modified and assigning them a temporary weight of
1, is greater than the target, then it is also not possible. - Suppose we can find a modifiable edge
(u, v)such that the length of the shortest path from source tou(dis1)plus the length of the shortest path fromvto destination (dis2) is less than target (dis1 + dis2 < target), then we can change its weight to “target - dis1 - dis2”. - For all the other edges that still have the weight
“-1”, change the weights into sufficient large number (target,target + 1or200000000etc.).
Solution:
We can break down the approach as follows:
Approach:
-
Initial Check with Existing Weights:
- First, we compute the shortest path from
sourcetodestinationusing only the edges with positive weights, ignoring the edges with weight-1. - If this distance is already greater than
target, then it's impossible to modify the-1edges to achieve the target, so we return an empty array.
- First, we compute the shortest path from
-
Temporary Assignment of Weight 1:
- Next, assign a temporary weight of
1to all edges with weight-1and recompute the shortest path. - If this shortest path is still greater than
target, then it's impossible to achieve the target, so we return an empty array.
- Next, assign a temporary weight of
-
Modify Specific Edge Weights:
- Iterate through the edges with weight
-1and identify edges that can be adjusted to exactly match the target distance. This is done by adjusting the weight of an edge such that the combined distances of paths leading to and from this edge result in the exacttargetdistance. - For any remaining
-1edges, assign a large enough weight (e.g.,2 * 10^9) to ensure they don't impact the shortest path.
- Iterate through the edges with weight
-
Return Modified Edges:
- Finally, return the modified list of edges.
Let's implement this solution in PHP: 2699. Modify Graph Edge Weights
<?php
private $kMax = 2000000000;
/**
* @param $n
* @param $edges
* @param $source
* @param $destination
* @param $target
* @return array|mixed
*/
function modifiedGraphEdges($n, $edges, $source, $destination, $target) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $graph
* @param $src
* @param $dst
* @return int|mixed
*/
function dijkstra($graph, $src, $dst) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
// Example 1
$n = 5;
$edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]];
$source = 0;
$destination = 1;
$target = 5;
print_r(modifyGraphEdgeWeights($n, $edges, $source, $destination, $target)); // Output: [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
// Example 2
$n = 3;
$edges = [[0,1,-1],[0,2,5]];
$source = 0;
$destination = 2;
$target = 6;
print_r(modifyGraphEdgeWeights($n, $edges, $source, $destination, $target)); // Output: []
// Example 3
$n = 4;
$edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]];
$source = 0;
$destination = 2;
$target = 6;
print_r(modifyGraphEdgeWeights($n, $edges, $source, $destination, $target)); // Output: [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
?>
Explanation:
- The dijkstra function calculates the shortest path from the source to all other nodes.
- We initially compute the shortest path ignoring
-1edges. - If the path without
-1edges is less than the target, the function returns an empty array, indicating it's impossible to adjust the weights to meet the target. - Otherwise, we temporarily set all
-1edges to1and check if the shortest path exceeds the target. - If it does, it's again impossible to reach the target, and we return an empty array.
- We then modify the weights of
-1edges strategically to achieve the desired shortest path of exactly target.
This approach efficiently checks and adjusts edge weights, ensuring that the target distance is met if possible.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2024-08-30T19:45:37+00:00) 2699. Modify Graph Edge Weights. Retrieved from https://www.scien.cx/2024/08/30/2699-modify-graph-edge-weights/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.