In yesterday's LeetCode Weekly Contest 346, nearly no contestant solved the 4th problem successfully. Here is the problem, Modify Graph Edge Weights:
Given an undirected, weighted, connected graph with n
nodes ($$$1 <= n <= 100$$$) and m
edges ($$$1 <= m <= \frac{n(n + 1)}{2}$$$). All edges have weight in $$$[1, 10^{7}]$$$, but some have weight $$$-1$$$, denoting that you are to assign that edge some positive weight in $$$[1, 2 * 10^{9}]$$$.
Now, you are also given two nodes source
and destination
, as well as a positive integer target
($$$1 <= target <= 10^{9}$$$). Find ANY assignment of edge weights that make the shortest distance from source
to destination
exactly target
, or report that there is no such assignment.
My own idea:
- Firstly, if the shortest distance from
source
todestination
is less thantarget
without considering any customizable edges (edges with weight $$$-1$$$), then the shortest distance will always be less thantarget
, so it's impossible. - Then, set all the customizable edge weights to $$$1$$$, the smallest possible. If the shortest distance from
source
todestination
is greater thantarget
, or if there is no path between them, then it's also impossible to make the shortest distance equal totarget
. - Otherwise, I think a valid assignment of edges weights should always exist. However, I haven't thought of a way to assign the edge weights to that the shortest distance always becomes exactly
target
; greedy algorithms, such as making all the customizable edge weights1
except for a single edge sometimes results in some other even-shorter path to exist, breaking the solution.
Could someone point me in the right direction?
Note that community-written solutions can be found here. The top-voted one seems promising, but one of the comments on it (from redsmolder
) claims a counterexample to the greedy solution given, and further claims that Dijkstra's algorithm is "unfit" for the problem (and that Floyd-Warshall is necessary).
Thank you all!