i'm looking algorithm i'm sure must have been studied, i'm not familiar enough graph theory know right terms search for.
in abstract, i'm looking algorithm determine set of routes between reachable vertices [x1, x2, xn] , starting vertex, when each edge has weight , each route can have given maximum total weight of x.
in more practical terms, have road network , each road segment length , maximum travel speed. need determine area can reached within time span starting point on network. if can find furthest away points reachable within time, use convex hull algorithm determine area (this approximates enough use case).
so question, how find end points? first intuition use dijkstra's algorithm , stop once i've 'consumed' 'budget' of time, subtracting budget on each road segment; stuck when algorithm should backtrack has used budget. there known name problem?
if understood problem correctly, initial guess right. dijkstra's algorithm, or other algorithm finding shortest path vertex other vertices (like a*) fit.
in simplest case can construct graph, weight of edges stands minimum time required pass segment of road. if have length , maximum allowed speed, assume know it. run algorithm starting point, pick vertices shortest path less x. simple that.
if want optimize things, note during work of dijkstra's algorithm, known shortest paths vertices increasing monotonically each iteration. kind of expected when deal graphs non-negative weights. now, on each step picking unused vertex minimum current shortest path. if path greater x, may stop. there no chance have vertices shortest path less x on.
if need determine points between vertices, vehicle can reach in given time, small extension above algorithm. next step, consider (u, v) edges, u can reached in time x, while v cannot. i.e. if define shortest path vertex w t(w), have t(u) <= x , t(v) > x. use basic math interpolate point between u , v coefficient (x - t(u)) / (t(v) - t(u)).
Comments
Post a Comment