#2699

Hard

auto_awesomeGraph plus Heap (Priority Queue)

LeetCode Problem Workspace

Modify Graph Edge Weights

Modify Graph Edge Weights is a graph problem where you adjust edge weights to match a target shortest path distance.

Problem Statement

You are given a weighted undirected connected graph with n nodes numbered from 0 to n - 1. The graph contains edges, where each edge is represented by an array [ai, bi, wi] denoting an edge between nodes ai and bi with weight wi. Some edges have a weight of -1, which means they are yet to be assigned a valid weight. Others have a positive weight.

The task is to modify the edges with weight -1, assigning them positive integer values within the range [1, 2 * 10^9], such that the shortest path from the source node to the destination node equals the given target value. If multiple solutions exist, any modification that achieves the target is correct. If it's impossible to achieve the target distance, return an empty array.

Examples

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

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: []

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

The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.

Constraints

1 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= ai, bi < n
wi = -1 or 1 <= wi <= 107
ai != bi
0 <= source, destination < n
source != destination
1 <= target <= 109
The graph is connected, and there are no self-loops or repeated edges

Solution Approach

Initial Feasibility Check

Start by checking if it's even possible to achieve the target shortest path distance. Use Dijkstra's algorithm to calculate the current shortest path between the source and destination, and analyze the existing weights to determine if the target is achievable.

Modify Edge Weights Using a Heap

For edges with weight -1, use a priority queue (heap) to greedily assign the minimum possible weights that still allow the shortest path to meet the target. Ensure that no modification leads to an invalid graph state or contradicts the target distance.

Handle Edge Cases

Ensure you handle edge cases like when there is no feasible way to modify the edges to achieve the target shortest path, returning an empty array in such cases. Also, ensure correctness when the graph contains multiple edges with weight -1.

Complexity Analysis

Metric	Value
Time	O(E \times (V + E) \log V)
Space	O(V + E)

The time complexity of the solution is O(E * (V + E) * log V), where E is the number of edges and V is the number of vertices, due to the priority queue operations during graph traversal. The space complexity is O(V + E) for storing the graph and maintaining the priority queue during the computation.

What Interviewers Usually Probe

Ensure the candidate applies graph traversal techniques like Dijkstra's or Bellman-Ford to efficiently solve the problem.
Look for the candidate's ability to implement priority queues and modify edge weights dynamically.
Evaluate how the candidate handles edge cases where the target distance is not achievable.

Common Pitfalls or Variants

Common pitfalls

Not checking the feasibility of achieving the target distance before attempting to modify edge weights.
Incorrectly assigning edge weights without considering their impact on the shortest path.
Overlooking edge cases where no valid solution exists and returning an empty array.

Follow-up variants

Extend the problem to allow negative weights and test how the algorithm handles this scenario.
Consider modifying the graph with additional constraints, such as limiting the total number of edge modifications.
Optimize the algorithm for larger graphs, improving efficiency with advanced graph traversal methods or heuristics.

FAQ

What is the primary technique to solve the Modify Graph Edge Weights problem?

The problem primarily involves graph traversal using algorithms like Dijkstra's combined with heap (priority queue) techniques to modify edge weights.

How do you ensure the shortest path matches the target?

By carefully adjusting the weights of edges with -1 and using a priority queue to maintain the shortest path, ensuring the target is met.

What happens if it's impossible to achieve the target distance?

If no valid modifications can achieve the target distance, the solution should return an empty array.

How do you handle multiple edges with weight -1?

Multiple edges with weight -1 should be handled by modifying them in a way that maintains the shortest path to the target, ensuring no conflicts arise.

What are the common mistakes in solving this problem?

Common mistakes include failing to check if achieving the target is possible, incorrectly modifying edge weights, and overlooking edge cases like unreachable targets.

terminal

Solution

Solution 1: Shortest Path (Dijkstra's Algorithm)

First, we ignore the edges with a weight of $-1$ and use Dijkstra's algorithm to find the shortest distance $d$ from $source$ to $destination$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

class Solution:
    def modifiedGraphEdges(
        self, n: int, edges: List[List[int]], source: int, destination: int, target: int
    ) -> List[List[int]]:
        def dijkstra(edges: List[List[int]]) -> int:
            g = [[inf] * n for _ in range(n)]
            for a, b, w in edges:
                if w == -1:
                    continue
                g[a][b] = g[b][a] = w
            dist = [inf] * n
            dist[source] = 0
            vis = [False] * n
            for _ in range(n):
                k = -1
                for j in range(n):
                    if not vis[j] and (k == -1 or dist[k] > dist[j]):
                        k = j
                vis[k] = True
                for j in range(n):
                    dist[j] = min(dist[j], dist[k] + g[k][j])
            return dist[destination]

        inf = 2 * 10**9
        d = dijkstra(edges)
        if d < target:
            return []
        ok = d == target
        for e in edges:
            if e[2] > 0:
                continue
            if ok:
                e[2] = inf
                continue
            e[2] = 1
            d = dijkstra(edges)
            if d <= target:
                ok = True
                e[2] += target - d
        return edges if ok else []

Continue Practicing

#2662 minimum cost of a path with special roads #2642 design graph with shortest path calculator #2577 minimum time to visit a cell in a grid