Boost logo

Boost Users :

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




Boost-users 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