Dijkstra shortest path algorithm with edge cost

9
votes

I have a directed, positive weighted graph. Each edge have a cost of use. I have only A money, i want to calculate shortest paths with dijkstra algorithm, but sum of edges costs on route must be less or equal to A.

I want to do this with most smallest Dijstra modification (if I can do it with small modification of Dijkstra). I must do this in O(n*log(n)) if I can, but i think i can.

Anyone can help me with this?

2
algorithmshortest-pathdijkstra
As per usual with homework questions - what do you have so far? - Stephen
Am I understanding the problem correctly: Each edge has a length and a cost, and you want to minimize the length with the extra constraint that the cost must be less than or equal to A. - Mark Byers
@Mark Byers: Yes, i want to do shortest path with this extra constraint for each path must be true. - Svisstack
@Svisstack: does the constraint apply to edges or paths? - outis
Must you absolutely use Dijkstra's algorithm, or are other approaches also acceptable? - IVlad

2 Answers

6
votes

https://www.spoj.pl/problems/ROADS/

The problem was given at CEOI '98 and its official solution can be found here.

0
votes

You don't really need to modify Dijkstra's algorithm to do this as the answer is equivalent to finding the shortest path and then accepting it if it's less than or equal to A.

Of course, you could always short circuit the inner loop if you visit a path with a cost more than A.

EDIT: With the clarification that you want to minimize cost AND distance, you can't do that without clarifying the solution you want. Do you want the cheapest path? Do you want the shortest path? Do you want some function of cost and distance? All of these determine what weighting function you should use for a particular edge.