Arjen Markus (15 august 2005) Here is a very simple algorithm to find the shortest paths in a graph from any node to any other node. The computation is done using "Floyd's algorithm" and it consists of two steps:

- Compute a matrix of indices (encodings of the shortest paths)
- Use that to construct the path from one node to the next

It uses Tcllib's struct::graph module to store the graph in a convenient way.

Of course there are more efficient algorithms, but this one is delightfully simple.

# shortest_path.tcl -- # Find the shortest path in a graph, using # Floyd's algorithm # package require struct # mkMatrix -- # Make a square matrix with uniform entries # Arguments: # size Size (number of columns/rows) of the matrix # value Default value to use # Result: # A list of lists that represents the matrix # proc mkMatrix {size value} { set row {} for { set i 0 } { $i < $size } { incr i } { lappend row $value } set matrix {} for { set i 0 } { $i < $size } { incr i } { lappend matrix $row } return $matrix } # mkPath -- # Use the resulting matrix to print the shortest path # Arguments: # indices Matrix of indices # names Names of the nodes # from The name of the node to start with # to The name of the node to go to # Result: # A list of intermediate nodes along the path # proc mkPath {indices names from to} { set f [lsearch $names $from] set t [lsearch $names $to] set ipath [IntermediatePath $indices $f $t] set path [list $from] foreach node $ipath { lappend path [lindex $names $node] } lappend path $to return $path } # IntermediatekPath -- # Construct the intermediate path # Arguments: # indices Matrix of indices # from The node to start with # to The node to go to # Result: # A list of intermediate nodes along the path # proc IntermediatePath {indices from to} { set path {} set next [lindex $indices $from $to] if { $next >= 0 } { set path [concat $path [IntermediatePath $indices $from $next]] lappend path $next set path [concat $path [IntermediatePath $indices $next $to]] } return $path } # floydPaths -- # Construct the matrix that encodes the shortest paths, # via Floyd's algorithm # Arguments: # distances Matrix of distances # lmatrix (Optional) the name of a variable to hold the # shortest path lengths as a matrix # Result: # A matrix encoding the shortest paths # proc floydPaths {distances {lmatrix {}}} { if { $lmatrix != {} } { upvar 1 $lmatrix lengths } set size [llength $distances] set indices [mkMatrix $size -1] set lengths $distances for { set k 0 } { $k < $size } { incr k } { for { set i 0 } { $i < $size } { incr i } { for { set j 0 } { $j < $size } { incr j } { set dik [lindex $lengths $i $k] set dij [lindex $lengths $i $j] set dkj [lindex $lengths $k $j] if { $dik == {} || $dkj == {} } { continue ;# No connection - distance infinite } if { $dij == {} || $dik+$dkj < $dij } { lset indices $i $j $k lset lengths $i $j [expr {$dik+$dkj}] } } } } return $indices } # determinePaths -- # Construct the matrix that encodes the shortest paths from # the given graph # Arguments: # graph Graph to be examined # key Name of the (non-negative) attribute) holding the # length of the arcs (defaults to "distance") # lmatrix (Optional) the name of a variable to hold the # shortest path lengths as a matrix # Result: # A matrix encoding the shortest paths # proc determinePaths {graph {key distance} {lmatrix {}} } { if { $lmatrix != {} } { upvar 1 $lmatrix lengths } set names [$graph nodes] set distances [mkMatrix [llength $names] {}] for { set i 0 } { $i < [llength $names] } { incr i } { lset distances $i $i 0 ;# Distance of a node to itself is 0 } foreach arc [$graph arcs $key] { set from [lsearch $names [$graph arc source $arc]] set to [lsearch $names [$graph arc target $arc]] set d [$graph arc get $arc $key] if { $from != $to } { lset distances $from $to $d } } puts $distances return [floydPaths $distances lengths] } # Small test -- # Construct a graph, make a matrix of distances out of it # and query a few shortest paths. Note: the graph is undirected, # so the arrows are doubled. # set names {A B C D E F G} set distances { { 0 7 3 {} {} {} {}} { 7 0 {} 8 {} {} 40} { 3 {} 0 12 4 {} {}} {{} 8 12 0 {} {} {}} {{} {} 4 {} 0 10 7} {{} {} {} {} 10 0 8} {{} 40 {} {} 7 8 0}} # Construct the graph: # set graph [::struct::graph] set names {A B C D E F G} set arcs { A B 7 A C 3 B D 8 B G 40 C D 12 C E 4 E F 10 E G 7 F G 8 } # # foreach n $names { $graph node insert $n } foreach {from to distance} $arcs { set arc [$graph arc insert $from $to] $graph arc append $arc distance $distance set arc [$graph arc insert $to $from] $graph arc append $arc distance $distance } # # Now that we have our graph, examine some shortest paths # # Note: the ordering of the nodes in the graph is not the # same as the order in which they were created! Hence the # call to [$graph nodes]. set indices [determinePaths $graph "distance" lengths] puts $indices puts [mkPath $indices [$graph nodes] A B] puts [mkPath $indices [$graph nodes] B G]

See also: A-star