Solve the graph problem with a specific limitation.

76 Views Asked by At

Assume that there are a set of roads that connect the cities between A and B. We model this as a graph of $n$ nodes (cities) connected by $m$ edges (roads). Each edge weight corresponds to the time it takes to travel along that road, so the edge weight for the road between city $u$ and the city $v$ is $w(u, v)$. There are two types of roads: free roads and roads with cost. All cost roads cost the same amount and are generally (although not always) faster than free roads. Bob would like to reach city B from A as fast as possible, however, he only has enough money to take at most one cost road.

How to find such a route?

1

There are 1 best solutions below

0
On BEST ANSWER

Create a layered network with two layers. Each layer has a copy of the original graph with just the regular roads. The toll roads correspond to directed edges from layer $1$ to layer $2$. Start at the copy of node $A$ in layer $1$, and end at the copy of node $B$ in layer $2$.