Shortest path for a weighted graph, but the weights are a bit special

user_10623560 0
Viewed 131

I am trying to find a shortest path (the cheapest) in a weighted multi-directional graph where the vertices are cities, the edges are routes between cities and the weights are prices.

each route/edge is owned by one of 3 companies. The price is the same for all edges owned by a company. So all edges owned by company 'A' will have a price of X.

So if a final path goes through 2 of company A's routes and 1 of company B's routes, then the final price is 2PriceofA + 1PriceOfB. Also the weight of a edge is simply the price of the associated company.

This is a normal case so far, however, the following extra rule is making it difficult for me:

The 3rd company 'C' applies it's price ONCE regardless of how many routes it has in the final path, but it's price is usually higher than the previous companies. Therefore C's routes are ideal for longer paths, while A and B are best for shorter paths.

Here is what i have done so far (and why it does not work):

I am using Dijkstra to get the cheapest path and i have simply set the weights of each edge to be the price of the company. Even for C.

Then if the algorithm visits a node owned by C, it sets the weight of all the other edges that C owns to 0. Otherwise the algorithm continues as normal.

The problem is that Dijkstras algorithm always prioritizes the immediate best choice, and since company A and B have smaller prices than C, then it will try to avoid C. Sometimes this results in a path that the algorithm thinks is the shortest/cheapest, but in reality could have been much cheaper if it had chosen C to begin with.

How can i get the true cheapest path in this case?

Should i change to another algorithm? and if so, which one?

shortest-path dijkstra algorithm
2 Answers

One option here is to transform the original graph of flights to directly encode the idea that once you’ve taken a C flight, all future C flights are free.

For each airport x, create two nodes x1 and x2. The idea is that node x1 corresponds to being in airport x without having ever taken a C flight, and x2 corresponds to being in airport x having taken at least one C flight.

Now add edges as follows. For each A or B flight from an airport x to an airport y at price p, add an edge from x1 to y1 at price p and from x2 to y2 at price p. These correspond to taking A and B flights at their established price. Then, for each C flight from an airport x to an airport y at price p, add an edge from x1 to y2 at price p (this is where you pay the one-time cost of using C flights) and from x2 to y2 at price 0 (this flight is free now that you’ve already paid the up-front cost to use C flights).

If you run Dijkstra’s algorithm in this modified graph starting at a node x1, you can find the cheapest flight to an airport y by looking at the costs to get to y1 (not using any C flights) and y2 (using at least one C flight). The paths through the new graph will tell you which flights to take.

This doubles the size of the input graph, which will slightly slow down Dijkstra’s algorithm but won’t asymptotically affect the runtime.

user_5015570

I think you can keep a flag alongside the costs to each node that indicates you have already used a C flight or not. This flag will dictate whether the next C flight costs you or not.

In other words, instead of setting all the C edges to zero when you use a C edge, keep this local to the state of each tried path.

You could prioritize paths where the flag is set over other paths with equal costs but with an unset flag. This is a heuristic that helps your algorithm find the solution faster, but it would have done so nonetheless eventually.

Now, when you start Dijkstra, paths with C cost included will come forward in the priority queue as soon as a multiple of A or B paths cost at leas as much as a C path that includes a C. From there it's just a standard Dijkstra as far as I understand.

user_77556650
Related