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 uses RoleMethod injection...

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

https://www.youtube.com/watch?v=psg2-6-CEXg

The code can be studied in situ in Ruby (dijkstra.rb) or in the HTML-file:

Ruby Dijkstra program listing.