Find path from node

Question

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).

Answer 1

Dijkstra's algorithm allows you to determine the shortest path from 1 to $N$ is time $O(E\log E)$. In particular, by considering only edges of weight at most $w$, you can check whether there exists a path of length at most $T$ in which the maximum weight edge is at most $w$.

You can now use binary search to find the optimal value of $w$. After spending $O(E\log E)$ time to sort the edge weights, the binary search involves $O(\log E)$ invocations of Dijkstra's algorithm, for a total running time of $O(E\log^2 E)$.