9

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?

Improve this question
10
  • 3
    As per usual with homework questions - what do you have so far? Commented Apr 26, 2010 at 0:28
  • 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. Commented Apr 26, 2010 at 0:29
  • @Mark Byers: Yes, i want to do shortest path with this extra constraint for each path must be true. Commented Apr 26, 2010 at 0:34
  • @Svisstack: does the constraint apply to edges or paths? Commented Apr 26, 2010 at 1:08
  • Must you absolutely use Dijkstra's algorithm, or are other approaches also acceptable? Commented Apr 26, 2010 at 13:42

2 Answers 2

Reset to default
5

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

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

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Perhaps i'm missing something here, but none of those links actually feature an algorithm that solves this problem. The SPOJ submissions contain algorithms, but we can't read the source code to them!
0

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.

Improve this answer

7 Comments

The cost and length of an edge are two different things, check out the comments.
@Bus He did not say anything about a length in his question. As far as I understand the only value associated with each edge is the cost.
Which of the many meanings Svisstack intended is still unclear to me as well, even after zhe answered Mark's question.
I think the discussion makes it clear. Mark asked: "Each edge has a length and a cost, you want to minimize the length with the extra constraint that the cost must be less than or equal to A." Svisstack answered yes.
@Bus: it's just that it wouldn't be the first time someone didn't understand a clarifying question, or the alternate meanings and ambiguities in the question.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.