Shortest path in graph where cost depends on the history of traversing

Question

My goal is to find the shortest path (lowest cost) between given cities (vertices) connected with roads (edges). Each road and each city has charge (cost) that has to be paid before entering that road/city.

If that would be whole task, I would use Dijkstra algorithm to find the shortest path (and add city cost to the cost of the road connected right before it).

BUT :

Cities have something like partnership agreements - when you visit and pay charge in one of them, entering rest of the cities in this particural partnership is free.

So, cost of the vertex (edge connected before it) depends on vertices that has been already traversed.

Is there any algorithm for that kind of problem?

Thank you.

Answer 1

You can reduce the set cover problem to this one. That means your problem is NP hard, and you shouldn't expect to find an efficient solution (in general).

That means you should hope that the number of partnerships is small, and perhaps then you can get away with considering all possible subsets of non-singleton road/city partnerships, and finding the shortest path for each (assuming that your path will go through only roads/cities in the given subset you're considering). Then your algorithm will run in 2^P * (N+M) time where P is the number of partnerships, and N and M are the number of cities and roads respectively.

For completeness, here's the reduction from set cover to your graph problem:

The set cover problem is that you're given a finite set S = {s[1], ..., s[n]}, and subsets of S: S[1], S[1], S[2], ..., S[N]. You're asked to find the minimal number of these subsets that cover S.

To use your city problem to find the minimal cover, construct a graph like this. Let the vertices of the graph be START, END, and pairs (S[i], t) where and t is in S[i]. Add edges in the graph between:

• START and (S[i], s[1]) for each S[i] with s[1] in S[i]
• (S[i], s[n]) and END for each S[i] with s[n] in S[i].
• (S[i], s[k]) and (S[i'], s[k+1]) for each k in 1...n-1 and for each S[i] and S[i'] which contain the corresponding elements.

Let the edge weights be all 1, and let the cost of entering (S[i], s) also be 1. All cities/vertices (S[i], s), (S[i], t) share the same cost. No two roads/edges share a cost.

Now, a lowest-cost path from START to END corresponds to finding the minimal set of S[i] that cover S. The cost of that path will be 1 + n + p where p is the size of the minimal cover.

Answer 2

Dijkstra is perfectly fine for this problem, if you model it properly.

By properly, I mean you need to recognize that the State of your Truck is not only is current location, but also its history.

class TruckState {
    City current;
    List<City> visited;
}

Note: the order may not matter if the entry fee is conservative (all cities within an agreement clause provide the same cost benefit, regardless of order?). If so, represent history as a Set, and you'll get smaller search-space:

class TruckState {
    City current;
    Set<City> visited;
}

---

All this makes your search space rather lage. You might recuce it further again if your parternship model allows it. For example, the useful state of the truck could be its location, and a Set of unlocked Agreements. If these unlockable agreements are fewer than the cities, you compress your state to its bare minimum.

class TruckState {
    City current;
    Set<Agreement> unlocked;
}

---

[EDIT]: It seems the order matters: you pay the entry fee to the First city of an agreement pool. You need to track which city of the agreement was visited first. Then I suggest the following state:

class TruckState {
    City current;
    Map<Agreement, City> visited;
}

Note: It will be very difficult to use A-star as finding an admissible Heuristic will be less than trivial. I cannot advise, as I don't know if your cost includs some type of distance function. As it stands, since costs may become zero depending on state, it might be that the only admissible Heurisitic is constant value 0. Not useful...

Answer 3

What you want to do here is clustering.

Before you start running Dijkstra or some other algorithm, run some changes on your graph where all the cities that have an agreement with each other are converted to one new node.
From this node you can reach any city that was reached from any one of the cities in it (choosing the cheapest edge of course).

This would be very similar to changing the charges of the relevant roads to 0 for edges that are between two cities who have an agreement.