It seems to me that dealing with references and and parallel decorations of references seems pretty complex for folk not expert in these things. A simpler approach may be to abstract away the graph representation and algorithms from the objects themselves and create a graph object proper with objects associated with the nodes.

This can probably be done most easily by using Graph::Directed to handle graph stuff and adding node number to the object's data to be set upon initialization. The module has all the (basic) graph methods you could want, with no worries about dereferencing, just simple method calls.