Problem

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.

Examples

Example 1:

graph TD

subgraph Input Graph
	0[0]
	1[1]
	2[2]
	3[3]
	4[4]
	
	0 ---|"-1"| 3
	2 ---|"-1"| 0
	4 ---|"-1"| 1
	4 ---|"-1"| 3
end

subgraph Output Graph
	A[0]
	B[1]
	C[2]
	D[3]
	E[4]
	
	A ---|"3"| D
	C ---|"1"| A
	E ---|"1"| B
	E ---|"1"| D
end

style 0 fill:#f96,stroke:#f66,stroke-width:2px;
style 1 fill:#9f9,stroke:#0f0,stroke-width:2px;
style A fill:#f96,stroke:#f66,stroke-width:2px;
style B fill:#9f9,stroke:#0f0,stroke-width:2px;
  
1
2
3

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:

 graph TD
 
 subgraph Input Graph
     0[0]:::source
     1[1]
     2[2]:::destination
 	
     0 ---|"-1"| 1
     0 ---|"5"| 2
 end
 
 subgraph Output Graph
     
 end
 
 style 0 fill:#f96,stroke:#f66,stroke-width:2px
 style 2 fill:#9f9,stroke:#0f0,stroke-width:2px
  
1
2
3

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:

 graph TD
 
 subgraph Input Graph
     0[0]:::source
     1[1]
     2[2]:::destination
     3[3]
 	
     1 ---|"4"| 0
     1 ---|"3"| 2
     2 ---|"5"| 3
     0 ---|"-1"| 3
 end
 
 subgraph Output Graph
     A[0]:::source
     B[1]
     C[2]:::destination
     D[3]
 	
     B ---|"4"| A
     B ---|"3"| C
     C ---|"5"| D
     A ---|"1"| D
 end
 
 style 0 fill:#f96,stroke:#f66,stroke-width:2px;
 style 2 fill:#9f9,stroke:#0f0,stroke-width:2px;
 style A fill:#f96,stroke:#f66,stroke-width:2px;
 style C fill:#9f9,stroke:#0f0,stroke-width:2px;
  
1
2
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.

Solution

Method 1 - Dijkstra Algorithm

The code aims to modify edges in an undirected weighted graph such that the shortest path from a given source to a destination equals a specified target distance. It specifically updates edges initially marked with a weight of -1 to achieve this.

Here are the steps:

  1. Building the Graph:
    • Uses buildGraph(int[][] edges) to create an adjacency list representation of the graph, excluding edges with a weight of -1.
  2. Initial Shortest Path Calculation:
    • Runs runDijkstra() to compute the shortest path distances from the source to all other nodes.
    • After the calculation, dist[destination] holds the shortest path distance from the source to the destination.
  3. Evaluating Initial Shortest Path:
    • If dist[destination] is less than target, the function returns an empty array, indicating it’s impossible to achieve the target distance.
    • If dist[destination] equals target, it returns the edges as is.
  4. Adjusting -1 Edges:
    • Iterates over the edges list to adjust edges with an initial weight of -1.
    • Sets an initial weight of 1 to each edge marked -1, then updates the adjacency list accordingly.
  5. Recalculate Shortest Path:
    • Re-runs runDijkstra() to recompute the shortest path distances after introducing the adjusted edge.
    • Checks if the new distance equals the target:
      • If it matches, returns edges where any remaining -1 weights are set to an upper bound.
      • If the new distance is less than the target, increments the edge weight such that the shortest path distance equals the target.
  6. Return Updated Edges:
    • If no feasible solution is found, returns an empty array. Otherwise, returns the modified edges.

Code

  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
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

public class Solution {
	static class Edge {
		int node;
		int wt;

		Edge(int node, int wt) {
			this.node = node;
			this.wt = wt;
		}
	}

	private static final int INF = Integer.MAX_VALUE;
	private int source;
	private Map<Integer, List<Edge>> graph;
	private int[] dist;


	public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
		this.source = source;
		this.graph = buildGraph(edges);

		this.dist = new int[n];

		runDijkstra();

		if (dist[destination] < target) {
			return new int[0][0];
		} else if (dist[destination] == target) {
			return fill(edges);
		}

		for (int[] edge : edges) {
			if (edge[2] == -1) {
				int u = edge[0];
				int v = edge[1];
				int wt = 1;
				edge[2] = wt;

				graph.putIfAbsent(u, new ArrayList<>());
				graph.putIfAbsent(v, new ArrayList<>());

				graph.get(u).add(new Edge(v, wt));
				graph.get(v).add(new Edge(u, wt));

				// Recalculate shortest path
				runDijkstra();

				if (dist[destination] == target) {
					return fill(edges); // found the target
				} else if (dist[destination] < target) {
					edge[2] += target - dist[destination];
					updateGraph(u, v, edge[2]);
					return fill(edges);
				}

			}
		}

		return new int[0][0];
	}

	private Map<Integer, List<Edge>> buildGraph(int[][] edges) {
		Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
		for (int[] edge : edges) {
			if (edge[2] == -1) {
				continue;
			}
			int u = edge[0];
			int v = edge[1];
			int wt = edge[2];
			graph.putIfAbsent(u, new ArrayList<Edge>());
			graph.putIfAbsent(v, new ArrayList<Edge>());

			graph.get(u).add(new Edge(v, wt));
			graph.get(v).add(new Edge(u, wt));
		}

		return graph;
	}

	private void runDijkstra() {
		Arrays.fill(dist, INF);
		dist[source] = 0;
		PriorityQueue<Edge> pq  = new PriorityQueue<>(Comparator.comparingInt(i -> i.wt));
		pq.add(new Edge(source, 0));

		while (!pq.isEmpty()) {
			int node = pq.poll().node;

			for (Edge nei : graph.getOrDefault(node, new ArrayList<>())) {
				int d = dist[node] + nei.wt;
				if (d < dist[nei.node]) {
					dist[nei.node] = d;
					pq.add(new Edge(nei.node, d));
				}
			}
		}
	}

	private int[][] fill(int[][] edges) {
		for (int[] edge : edges) {
			if (edge[2] == -1) {
				edge[2] = (int) (2 * 1e9);
			}
		}
		return edges;
	}


	private void updateGraph(int u, int v, int wt) {
		graph.get(u).removeIf(e -> e.node == v);
		graph.get(v).removeIf(e -> e.node == u);
		graph.get(u).add(new Edge(v, wt));
		graph.get(v).add(new Edge(u, wt));
	}
}

Complexity

  • ⏰ Time complexity: O(E.(E+V) log V) where E is number of edges and V is number of vertices
    • Building graph takes O(E) time
    • Running Dijkstra’s algorithm initially (in the runDijkstra method) takes (O((V + E) \log V)),
    • Then for each edge e with -1 weight, we run dijkstra’s algorithm again, and in worst case it will be E such edges, hence it is O(E.( E+V) log V
  • 🧺 Space complexity: O(E+V)
    • For storing graph it takes O(E+V)
    • Distance array takes O(V)