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

Subject: [Boost-users] Modifying Dijkstra's Shortest Paths algorithm in Boost::Graph to not relax certain edges
From: Artyom (sneg.vx_at_[hidden])
Date: 2009-04-21 13:36:52

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