# For graph $G$, vertices $s,t$ find the shortest path between $s$ and $t$ by weight among all the shortest paths by edges

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.

• Let me see if I get this straight: You can find in linear time a list of the shortest paths (by edges). You want to find the shortest path from this list by weight. Why don't you just calculate the lengths of the paths on your list and interpret this as finding the largest element in a list? Also, you say linear algorithm, and do you mean linear in the number of vertices? Or linear in the number of vertices times the number of edges? Aug 28, 2012 at 21:07
• @mixedmath: The OP can find the graph of all shortest paths by edges in linear time. But there may be exponentially many paths in this graph. Aug 28, 2012 at 21:27
• Ah yes, you're right. So run another Bellman Ford, as it can't take any longer than the original computation. But I still wonder, linear in what? Bellman Ford uses $O(|V||E|)$ time, so are we talking about linear in $|V||E|$? Aug 28, 2012 at 21:35
• I think that Jozef is using BFS to mean "breadth-first search", not "Bellman–Ford search". Aug 28, 2012 at 21:43

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