Given directed graph $G=(V,E)$, two vertices and a weights function $w: E \to R$. In addition we know that there aren't negative cycles in $G$. I need to find a linear algorithm that finds among the shortest paths by edges from $s$ to $t$ the shortest path by weight.
I can find the graph of all shortest paths from $s$ to $t$ by two BFS (for $s$ and from $t$ on $G^T$- a version of BFS which does not get rid of edges of subsequent levels), but then how do I find in linear time the shortest path by weight? I need to use Bellman-Ford for that, no?
Thanks a lot.
Best Answer
All the shortest paths by edges have the same length, so if you add $w$ to every edge it won't change the shortest path by weight. Choose a large enough $w$ so that every edge is positive, and then run Dijkstra's algorithm. (But this would still not quite be linear, since Dijkstra's algorithm runs in $O(\lvert E\rvert + \lvert V\rvert\ {\rm log}\ \lvert V\rvert)$).