Modifying Dijsktra's algorithm to work with edges having more than one possible cost

Question

We have a directed weighted graph where an edge between two nodes can have more than one possible cost value (more precisely, at most 2 costs). I need to use a time-dependent variant of the Dijkstra's algorithm that can handle two possible ways of getting from one node to another, the cost between the nodes (edge cost) being dependant on the time at which we arrive at the source node and the type of edge we are about to use. When traversing from one node to the other only one of these edges is picked and its cost is added to the same total cost.

I currently model the two possible costs for an edge as two separate edges between the same nodes.

There is a similar problem I found here and it was suggested to augment the graph by duplicating the nodes. However, this does not allow returning to the original graph and implies the overhead of, well, duplicating all the nodes and possibly edges between them and original nodes.

Do you have any suggestions as to how to tackle this problem with as little overhead as possible? (The original graph is expected to be huge)

Thanks

Edit: I provided more details about the problem in the first paragraph

Answer 1

You can safely ignore the largest of the two costs for algorithm purposes.

Assume there is a shortest path the uses the largest cost between two vertices, you can change it to use the smallest cost and the path will cost less, and that contradicts the assumption.

Answer 2

I think you can hack step 3 of Dijsktra's algorithm :

For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.

In your setup, you have two distances from A to B, depending on how late it is. You use the second one if your current distance to A is above your time treshold.

This step becomes :

if current distance to A above threshold :
    current distance to B = min(current distance to B, current distance to A + d2(A, B)) 
else:
    current distance to B = min(current distance to B, current distance to A + d1(A, B))