How do I implement Dijkstra's on a graph with 2 given edge weights with condition to use the other one?
I am stuck in a problem where I cannot figure out how to apply Dijkstra's algorithm to find the shortest distance between A and C when each edge have 2 weights and the second weight (on the right) can only be used as the edge weight if we visit any of the underlined nodes, else we only use the first weight as the edge weight.
I tried solving it using normal Dijkstra's but got stuck as it does not move forward to loop back to A and return the shortest path from A to C.
Consider the first weights as the time taken by your SUV to an edge and second weight as the time taken by another car which is a small car to reach a node. You can only change cars on the underlined nodes and once you sit in a small car you can take the second weight as the time taken, but if the second time is bigger than first time you can also use the time one in the small car.
use this picture for below answer
The shortest path from a to c should be [A,D,E,A,D,C] 270 min
Duplicate the graph 𝐺 as graph 𝐺', and make these changes:
- In 𝐺, remove the second edges, so that it only has the first edges
- In 𝐺', remove the first edges, so that it only has the second edges
- For every underlined vertex 𝑢 in 𝐺, add a directed edge with weight 0 from 𝑢 to its copy vertex 𝑢' in 𝐺'. Add also such a zero-weight edge from 𝐶 to 𝐶'.
Perform Dijkstra's algorithm to find the shortest path from 𝐴 to 𝐶'. Map the found path to a path in the original graph, removing the (𝑢,𝑢') step from it, and the "accents".