P is for Practical | |
PerlMonks |
Calculating Shortest Paths with Graph::Directedby arunhorne (Pilgrim) |
on Jul 19, 2002 at 11:36 UTC ( [id://183192]=perlquestion: print w/replies, xml ) | Need Help?? |
arunhorne has asked for the wisdom of the Perl Monks concerning the following question: Monks, I have written the following code that creates a graph using the Graph::Directed package and generates a distance matrix accordingly:
The following output is produced:
The distance matrix is exactly correct apart from the diagonal (E1-E1, E2-E2, E3-E3). By correct I mean it isn't the result I want as it is correct in terms of graph theory. What I want is for the cell E1,E1 = 3, the cell E2,E2 = 1 and E3,E3 = 1. Obviously the distance from E1->E1 is zero as the start nodes and end nodes are equal - however, I wish to intorduce the constraint that the search must leave the start node before returning (a domain specific feature of the problem). The required matrix therfore is below:
Thus to get from E1->E1 in the above graph you must go E1->E2->E3->E1, the distance of which equals 3 (all arcs have a weight/cost of 1) as required. The corresponding paths for E2 and E3 have a distance of just 1 because they have self referencing arcs. The question: can anyone think of a way of obtaining the required result (and thus placing the constraint on the algorithm) with the minimum effort - preferably whilst staying within the bounds of Graph::Directed. Best wishes, ____________Arun
Back to
Seekers of Perl Wisdom
|
|