Leetcode Daily Question 30/08/2024 - 2699. Modify Graph Edge Weights

Problem Description:

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.

import heapq
from typing import List
from collections import defaultdict
class Solution:
  def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
    adjacency_list = defaultdict(list)
    for i, (node, connection, weight) in enumerate(edges):
      adjacency_list[node].append((connection, i))
      adjacency_list[connection].append((node,i))
      
    distances = defaultdict(lambda: [float('inf'), float('inf')])
    distances[source][0] = distances[source][1] = 0
    
    self.dijkstra(adjacency_list, edges, source, distances, 0, 0)
    diff = target - distances[destination][0]
    
    if diff < 0:
      return []
    
    self.dijkstra(adjacency_list, edges, source, distances, diff, 1)
    
    if distances[destination][1] < target:
      return []
    
    for edge in edges:
      if edge[2] == -1:
        edge[2] = 1
    
    return edges
  
  
  
  def dijkstra(self, adj, edges, source, distances, diff, run):
    n = len(adj)
    min_heap = [(0, source)]
    distances[source][run] = 0
    
    while min_heap:
      curr_dist, node = heapq.heappop(min_heap)
      if curr_dist > distances[node][run]:
        continue
        
      for neighbour, index in adj[node]:
        weight = edges[index][2]
        if weight == -1:
          weight = 1
        if run == 1 and edges[index][2] == -1:
          new_weight = diff + distances[neighbour][0] - distances[node][1]
          if new_weight > weight:
            edges[index][2] = weight = new_weight
            
        n_weight = distances[node][run] + weight
            
        if distances[neighbour][run] > n_weight:
          distances[neighbour][run] = n_weight
          heapq.heappush(min_heap, (distances[neighbour][run], neighbour))

Explanation:

This question is rather tricky. The idea is to utilise Dijkstra's algorithm to find the shortest path and modify the path weight if necessary.

So we need 2 things:
- A modified Dijkstra's to handle edge modification
- 2 passes of Dijkstra's to
1. to calculate the shortest path without modification to the actual graph
2. using the established distances to calculate the required modification to the actual edges.

To start, we model the undirected graph as an adjacency list and the index of the node we are looking at.

adjacency_list = defaultdict(list)
for i, (node, connection, weight) in edges:
  adjacency_list[node].append((connection, i))
  adjacency_list[connection].append((node,i))

Then we can initiate another list of lists to capture the path distances. Each list contains 2 distances, first is without modifications (note: we use the place holder '1' as our initial distance if the weight is unknown or '-1'), then is with modifications. We can also set the distance at our source as 0.

distances = defaultdict(lambda: [float('inf'),float('inf')])
distances[source][0] = distances[source][1] = 0

Then comes our first pass. This calculates the shortest path from source to destination without modifying the graph.

We then check if the distance is larger than the target. If so, we cannot proceed further and we return an empty list.

self.dijkstra(adjacency_list, edges, source, distances, 0 ,0)
diff = target - distances[destination][0] 
if diff < 0:
  return []

Then we do our second pass of dijkstra. This time we check if our shortest path equals to our target, if not then we have an invalid path, and we return an empty list.

We do a final check of the edges and replace any unknown and unused edges with '1'.

self.dijkstra(adjacency_list, edges, source, distances, diff, 1)
diff2 = target - distances[destination][1]
if diff2 > 0:
  return []

for edge in edges:
  if edge[2] == -1:
    edge[2] = 1

return edges

Now we tackle the dijkstra function. We use a min heap to find our shortest path. How Dijkstra's algorithm works is by exploring all neighbours of a node to decide the shortest path possible to take.

To modify the edge weight, we temporarily change all the unknown weights to '1'. Then we can add the max amount of weight to the first edge we are allowed to modify to make it equal to the target.

def dijkstra(adj, edges, source, distances, diff, run):
    n = len(adj)
    min_heap = [(0, source)]
    distances[source][run] = 0 #initial distance at source is 0.
    
    while min_heap:
      curr_dist, node = heapq.heappop(min_heap)
      if curr_dist > distances[node][run]: # this means we have found a shorter path, we can skip curr_dist.
        continue
        
      for neighbour, index in adj[node]:
        weight = edges[index][2]
        if weight == -1: #place holder '1'.
          weight = 1
        if run == 1 and edges[index][2] == -1:
          new_weight = diff + distances[neighbour][0] - distances[node][1] # max weight that should be added.
          if new_weight > weight:
            edges[index][2] = weight = new_weight #modify the edge weight.
            
        n_weight = distances[node][run] + weight
            
        if distances[neighbour][run] > n_weight: # the shortest path currently.
          distances[neighbour][run] = n_weight
          heapq.heappush(min_heap, (distances[neighbour][run], neighbour))

The time complexity is O((V+E) * log(V)), where V is number of vertices, and E is number of edges. This is because during Dijkstra's, each vertex can be extracted from the heap at most once, and each edge is relaxed at most once. Each extraction operation takes O(log V) time for a min heap.

The space complexity is O(V+E), where V is number of vertices, and E is number of edges. This is because we need to create the adjacency_list and distances list for each node and their connections.

The full solution can be found near the top of the page.