tcl.tcl 899 B

12345678910111213141516171819202122232425262728293031323334353637383940
  1. proc dijkstra {graph origin} {
  2. # Initialize
  3. dict for {vertex distmap} $graph {
  4. dict set dist $vertex Inf
  5. dict set path $vertex {}
  6. }
  7. dict set dist $origin 0
  8. dict set path $origin [list $origin]
  9. while {[dict size $graph]} {
  10. # Find unhandled node with least weight
  11. set d Inf
  12. dict for {uu -} $graph {
  13. if {$d > [set dd [dict get $dist $uu]]} {
  14. set u $uu
  15. set d $dd
  16. }
  17. }
  18. # No such node; graph must be disconnected
  19. if {$d == Inf} break
  20. # Update the weights for nodes\
  21. lead to by the node we've picked
  22. dict for {v dd} [dict get $graph $u] {
  23. if {[dict exists $graph $v]} {
  24. set alt [expr {$d + $dd}]
  25. if {$alt < [dict get $dist $v]} {
  26. dict set dist $v $alt
  27. dict set path $v [list {*}[dict get $path $u] $v]
  28. }
  29. }
  30. }
  31. # Remove chosen node from graph still to be handled
  32. dict unset graph $u
  33. }
  34. return [list $dist $path]
  35. }