Suppose you have a graph with weighted edges and want to find the shortest path, but with an additional caveat, there are additional constraints that must be satisfied based on other properties of the previous edges. The best example I can think of is a flight or bus type. Where the nodes are cities and the edges are flights/routes, and for example, the edge weights are a price. Now you want to find the cheapest ticket, but you can't take a bus or a plane that leaves before your current bus/plane arrives. So in this example, you might have something like a list of tuples (city1, city2, price, duration, departure) and the goal would be to find the cheapest "feasible" route where in order to take edge e the departure_time>culmative_time. I cannot think of any really good or efficient solution.
0
votes
If you are trying to find the cheapest trip, while factoring in that you must wait for the next available "edge", ie. landing at an airport and waiting 30 minutes for the bus, you could simply use Dijkstra's Algorithm. Along with the usual parts of the algorithm, you would just have to note the time waited at each vertex.
- Josh Evans
1 Answers
0
votes
Use Dijkstra's algorithm. However, every time you travel to a new vertex along an edge, update the cumulative time to that vertex.
Any edge heading out of that vertex that is no longer currently being offered (total time exceeds it's offered time), are deleted.
Any edge heading out of that vertex that is not currently offered but will be offered in due time, add that time required to wait along with the time of travel to the next vertex, if the edge is found to be the next cheapest edge.
