BB7 - the Dijkstra Algorithm


The Dijkstra Algorithm computes the shortest path to all nodes from a given origin node in a network of Nodes and Edges. This solution is based on James Coplien's solution written in Ruby. The network is a modified and simplified Manhattan geometry The solution uses recursion rather than a loop.

This solution is noteworthy because two Roles(EastNeighbor and SouthNeighbor) have RoleMethods with the same name (recomputeTentativeDistance). These Roles are played by instances of the same class. There is no name conflict because Squeak/BabyIDE no longer used RoleMethod injection..

The mechanism for computing the path uses a simple mechanism illustrated in

http://www.youtube.com/watch?v=psg2-6-CEXg&feature=related

The code can be studied in situ in Squeak/DCI (BabyIDE.ZIP) or in the HTML-file

BB7Dijkstra listing.