Modified Djikstra's algorithm
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