title: Modifying Dijsktra's algorithm to work with edges having more than one possible cost
body: <p>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.</p>
  
  <p>I currently model the two possible costs for an edge as two separate edges between the same nodes.</p>
  
  <p>There is a similar problem I found <a href="https://stackoverflow.com/questions/14104718/shortest-path-with-one-edge-turn-to-zero">here</a> 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.</p>
  
  <p>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)</p>
  
  <p>Thanks</p>
  
  <p>Edit:
  I provided more details about the problem in the first paragraph</p>