Let $G = (V; E)$ be a directed graph where some subset of the vertices are coloured blue and each edge has a non-negative length. Provide an $\operatorname{O}(|E| \log n)$ time algorithm for finding the length of the shortest path from each vertex in the graph to its nearest blue vertex.

My biggest problem is being able to do this in the specified time. I could go down all edges of the starting vertex, then down the edges of each of those vertices, until I find a blue vertex. And then when I find it, save the path. But that won't work because it won't be fast enough, so any help would be appreciated, thanks!

EDIT: Shortly after posting this, I realized I can use Dijkstra's Algorithm.

  • 2
    $\begingroup$ Yes, adopt Dijkstra. The only trick is, it runs in $O(m + n \log n)$ only if you use Fibonacci Heaps... $\endgroup$ – gt6989b Sep 21 '15 at 20:04
  • $\begingroup$ You should expand your edit and post it as an answer to your own question. That way this post doesn't go on the unanswered questions queue. $\endgroup$ – Mike Pierce Sep 21 '15 at 21:50

Your Answer

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

Browse other questions tagged or ask your own question.