I have a question where I need to find a path from node 1 to node N in an undirected graph given weights in O(A Log^2 A)
.
The total cost of each path must not exceed T
amount of total weight.
For no1, you cannot use this path because its total cost is more than
13.
For no2 and no3, you only can use no2 because the maximum weight(7)
of no2 is smaller than the maximum weight(8)
of no3. So I am expected to print out 7
as a final answer.
I understand that this problem is quite similar to the Widest Path Problem
But the problem here cannot use Prims
or Kruskal
because the route chosen might not include the path that is expected.
The current solution I have would be to use DFS and find all the possible paths and attempt to compare the weights. I have no idea how would I complete within the O(A Log^2 A)
.