Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  mixedmath Aug 28 '12 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. –  Gareth Rees Aug 28 '12 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|$? –  mixedmath Aug 28 '12 at 21:35
    
I think that Jozef is using BFS to mean "breadth-first search", not "Bellman–Ford search". –  Gareth Rees Aug 28 '12 at 21:43
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.