4
$\begingroup$

So, I'm trying to conceptualize something:

Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats:

  1. movements on the graph are regulated by a circular cycle of length 48, in such a manner that:

    cycle{

         0 <= L <= 24  movement IS possible

    25 <= L <= 48 movement IS NOT possible

    }

    For simplicity's sake, we will call this cycle 'time'.

  2. The distance between nodes A and B is equal to:

    shortest_distance(A to B) - 1 OR shortest_distance(A to B) + 1

    Depending on their orientation

  3. the weight of the edges represents the 'time' it takes to travel between nodes.

I'd like to create an algorithm that will give me the shortest path with these constraints in mind, assuming one is leaving from node A at time(cycle) = 12, traveling towards node B. The shortest path would be defined as the path which takes the least 'time'.

Step one would obviously be to take into account the orientation affecting the shortest distance (i.e. which way are they oriented by above), which would be a simple addition or substraction to the result of djikstra's algorithm

What I'm having trouble figuring out is how to account for the cycle in the algorithm... could it be as simple as just an if statement checking to see if the current cycle time is within the constraints that allow movement?

Would my idea be viable? If not, does anyone h ave any suggestions at different ways I should look at this problem?

I know this question seems really basic, but I just can't wrap my head around it.

Improve this question
$\endgroup$
5
  • $\begingroup$ 2) seems to be circular; please clarify. $\endgroup$
    – Raphael ♦
    Apr 18, 2012 at 5:47
  • $\begingroup$ So it's almost like cities in a different timezone. I.E. Say A is a city in the CST (central standard time) timezone, and B is a city in the EST (eastern standard time) timezone. Travel 'time' from A to B, then, would be the actual travel time between the cities, plus one hour (because City B is in a timezone that is one hour ahead of City A). E.G. You leave city A at 12:00 PM and arrive at city B at 4:00 PM... travel time between the cities was only three hours from time of departure, but arrival time was four hours from time of departure. $\endgroup$
    – gfppaste
    Apr 18, 2012 at 13:51
  • $\begingroup$ @gppaste: You still express the distance in terms of the distance. Are you referring to two different quantities there? $\endgroup$
    – Raphael ♦
    Apr 18, 2012 at 18:31
  • $\begingroup$ I've read this a couple times. I'm not sure I understand your formulation, especially (1). $\endgroup$
    – Joe
    Apr 19, 2012 at 2:59
  • $\begingroup$ Might it be an idea you tell us your original problem (this sounds like an attempt at abstracting from some timezone related problem) so we can figure out exactly what you mean? $\endgroup$
    – Alex ten Brink
    Apr 19, 2012 at 12:27

1 Answer 1

Reset to default
3
$\begingroup$

I didn't really understand your problem description, but if you go by the timezone analogy, the only thing stopping you from using Djikstra's algorithm are the negative costs on some edges (ie.: some edges go back in time). If this is the problem, you can get around it by using an alternate algorithm that can handle negative edges, like Bellman-Ford

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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