2
$\begingroup$

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.

  • 0
    I think that Jozef is using BFS to mean "breadth-first search", not "Bellman–Ford search".2012-08-28

2 Answers 2

4

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

2

Isn't this a job for Floyd-Warshall algorithm

In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, Roy–Warshall algorithm, Roy–Floyd algorithm, or the WFI algorithm) is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights) and also for finding transitive closure of a relation R. A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices, though it does not return details of the paths themselves

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm