Re: [Boost-users] Modifying Dijkstra's Shortest Paths algorithm in Boost::Graph to not relax certain edges

Subject: Re: [Boost-users] Modifying Dijkstra's Shortest Paths algorithm in Boost::Graph to not relax certain edges
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2009-04-22 07:11:52

Artyom wrote:
> Hi,
> 
> I am using Boost::Graph and DSP which comes with it to work out shortest 
> paths around my graph. The problem is there is a certain exceptional 
> situation when certain vertices can become unreachable along certain 
> paths. I.e. although there is a valid distance value for edge B → C, the 
> same edge can become invalid if B is reached along a specific path. If 
> this happens, I want DSP to reject that edge. I attempted to create a 
> list of visitors. EdgeRelaxed records how vertices in the DSP queue were 
> reached. EdgeExamined checks for the exceptional situation and if it's 
> detected, it temporarily changes the distance value of the edge in 
> question to infinity. EdgeNotRelaxed then restores the distance value to 
> it's original.
> 
> Unfortunately this approach doesn't seem to work, I think the reason for 
> this is because dijkstras_shortest_paths() function gets information 
> about distances from the weight_map which is passed to it.
> 
> Is there any way I can modify the values inside the weight_map in 
> between DSP stages to invalidate certain paths which will result in them 
> being rejected for relaxation? Or perhaps there is an easier and tidier 
> way of achieving the same result?
> 
> Thanks in advance,
> Arty

Arty,

I think the following trick may help. You can create a "dynamic 
bundled_property_map" such that given a map "pm" and an edge descriptor 
"e" the construction "pm[e]" is actually a call of member function from 
the Bundle class. See attached example.

Good luck,
Dmitry