Modified Djikstra's algorithm

Question

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.

Answer 1

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