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

  • 2
    $\begingroup$ You're trying to find a path of minimum maximal weight among paths of weight at most $T$. Perhaps you can make that clear in the problem statement. $\endgroup$ – Yuval Filmus Feb 20 '19 at 7:59
  • $\begingroup$ You can perform binary search on the maximal weight in the path. For each weight $w$, run Dijkstra to calculate the shortest path from 1 to $N$ using only edges of weight at most $w$, and compare the answer to $T$. $\endgroup$ – Yuval Filmus Feb 20 '19 at 8:01
  • $\begingroup$ What is your estimate for the running time? $\endgroup$ – Yuval Filmus Feb 20 '19 at 10:49

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

| cite | improve this answer | |
  • $\begingroup$ I don't think you need my help to answer this question. $\endgroup$ – Yuval Filmus Feb 20 '19 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy