You also may try to use filtered graph adaptor http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/filtered_graph.html
Thank you Dmitry, but I can't use the filtered graph, because it completely hides edges; instead I would to hide an edge if I "come" from a particulary adjacent edge, and to show an edge if I come from another adjacent edge. In this other graph (I hope it's comprehensible...): _C _F o| /| o / o / A---->B------> D o o o >G \ ^ \ \ | \ _\| | _\| E | H I if the exploration goes through AB, and then BD, I can't go in DG, but only in DF and DH; instead if I come from ID, so I can go in DG. It is an exploration problem. I think that a Dijkstra/BFS foundation is that the graph must be immutable during the exploration. Instead I would to hide the DG edge in some cases, and to show it in other cases. Best regards, Cosimo Calabrese.