
Boost Users : 
From: Alex HagenZanker (a.hagenzanker_at_[hidden])
Date: 20201218 09:35:08
>>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 HagenZanker <a.hagenzanker_at_[hidden]<mailto:a.hagenzanker_at_[hidden]>> 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net