Re: [Boost-users] [BGL]Using a function for weightmap to dijkstra_shortest_path

Subject: Re: [Boost-users] [BGL]Using a function for weightmap to dijkstra_shortest_path
From: alex (alexhighviz_at_[hidden])
Date: 2015-11-25 06:55:22

>-----Original Message-----
>From: Boost-users [mailto:boost-users-bounces_at_[hidden]] On Behalf Of
>Amit Prakash Ambasta
>Sent: 23 November 2015 08:20
>To: boost-users_at_[hidden]
>Subject: [Boost-users] [BGL]Using a function for weightmap to
>dijkstra_shortest_path
>
>Hi,
>
>
>I am trying to write use BGL.dijkstra to calculate a shortest path in a time
>dependent network where edge.cost C(u, v) is a function of
>distance_at_edge.source and a variable wait time dependent on Edge.departure
>i.e.
>

Are you confident that you can use Dijkstra Shortest Paths for this? To me it seems that would only be possible if you knew that delay times are increasing over time, but not when they are fluctuating up and down.

The code might be simpler if you put the dynamic part in the combine functor instead of the weight map. 

using Time = double;
using Money = double;

struct Distance 
{
    Time time;
    Money cost;
};

struct Weight
{
    Time duration;
    Money cost;

    Time delay(cost Time& start) const 
    {
          // delay as a function of start time
    }
};

struct Combine
{
    Distance operator()(const Distance& start, const Weight& weight) const
    {
        Distance finish;
        finish.time = start.time + weight.delay(start.time) + weight.duration;
        finish.cost = start.cost + weight.cost;
        return finish; 
    }
};