>>In a way, yes. But I don't see where dijkstra would fail here given the >>weights are always positive. A regular bfs from a given start time should >>populate the distances to all nodes, identical to dijkstra
I think you are right, as long as you cannot get a better connection by arriving later. The combine function is supposed to combine a distance and a weight, typically these are the same type. Perhaps you are better off incorporating the waiting time in your weight property map. You might be able to do this using the function_property_map (https://www.boost.org/doc/libs/1_59_0/libs/property_map/doc/function_property_map.html ). Or to create your own property map, similar to this: template<class G, class DistanceMapType, class TravelTimeMapType> class weightmap { using distance_type = int; using weight_type = int; public: using key_type = Edge<G>; using value_type = weight_type; using reference = weight_type; using category = boost::readable_property_map_tag; weight_type get(const Edge<G>& e) const { weight_type travel = get(travel_time_map,e); distance_type distance = get(distance_map, boost::source(e)); weight_type wait = 60 - distance % 60; // assuming hourly service return travel + wait; } private: DistanceMapType distance_map; // total time to each vertex TravelTimeMapType travel_time_map; // time to travel over each edge }; template<class G> int get(const weightmap<G>& w, const Edge<G>& e) { return w.get(e); }. On Fri, Dec 18, 2020 at 6:39 AM Alex Hagen-Zanker <a.hagen-zan...@surrey.ac.uk<mailto:a.hagen-zan...@surrey.ac.uk>> wrote: >My actual use case is where weights represent nodes in a transport system and >for a person arriving at a vertex at some time Tx, there is a variable weight >of using the next outbound transport = waiting_time + travel_time, where >waiting_time is a function of Tx. That sounds like you intend to calculate a *dynamic* shortest path, which is not what Dijkstra's algorithm does for you. I know it doesn't answer your question, but I think it is more pertinent. Kind regards, Alex
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
