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.