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:
movements on the graph are regulated by a circular cycle of length 48, in such a manner that:
0 <= L <= 24 movement IS possible 25 <= L <= 48 movement IS NOT possible
For simplicity's sake, we will call this cycle 'time'.
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
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.