Algorithm for determining the largest coverage area
I'm looking for an algorithm that I'm sure needs to be learned, but I don't know enough about graph theory to even know the correct search terms.
In the abstract I am looking for an algorithm to determine a set of routes between reachable vertices [x1, x2, xn] and some initial vertex, when each edge has a weight and each route can only have a given maximum total weight x.
More practically, I have a road network and for each road segment the length and maximum speed. I need to define an area that can be reached within a certain period of time from any starting point on the network. If I can find the farthest points that are reachable in this time, then I will use a convex hull algorithm to determine the area (this is rough enough for my use case).
So my question is, how do I find these endpoints? My first intuition was to use Dijkstra's algorithm and stop as soon as I “consume” a certain “budget” of time, subtracting from that budget for each segment of the road; but I get stuck when the algorithm should return but used my budget. Is the name of this problem known?
source to share
If I understood the problem correctly, your initial guess is correct. Dijkstra's algorithm or any other algorithm that finds the shortest path from a vertex to all other vertices (for example, A *).
In the simplest case, you can plot a graph where the edge weights represent the minimum time it takes to traverse that section of road. If you have a length and a maximum speed allowed, I assume you know that. Run the algorithm from the starting point, select those vertices with the shortest path x
. So simple.
If you want to optimize things, note that as Dijkstra's algorithm runs, the currently known shortest paths to the vertices increase monotonically with each iteration. What is the kind of expectation when you are dealing with charts with non-negative weights. Now at each step you choose an unused vertex with the minimum current shortest path. If this path is longer than x
, you can stop. There is no chance that you have all the peaks with the shortest path less x
from now on.
If you need to pinpoint the points between vertices that a vehicle can reach at a given time, this is just a small extension of the above algorithm. As a next step, consider all the edges (u, v)
where it u
can be reached in time x
and v
cannot. That is, if we define the shortest path to the top w
as t(w)
, we have t(u) <= x
and t(v) > x
. Now use basic math to interpolate a point between u
and v
with a factor (x - t(u)) / (t(v) - t(u))
.
source to share
Using the width of the first search from the starting node seems to be a good way to solve the problem in O (V + E) time complexity. Okay, what Dijkstra does, but he stops after finding the smallest path. In your case, however, you must continue to collect routes for your route set until the route can be increased if its weight is less than or equal to the maximum total weight.
And I don't think there is a rollback in Dijkstra's algorithm.
source to share