Sha256: 02c4f7c5681443e9b8d5dbf5acc1521dca0004a56b5141107450d8a125e08a1a
Contents?: true
Size: 899 Bytes
Versions: 17
Compression:
Stored size: 899 Bytes
Contents
proc dijkstra {graph origin} {
# Initialize
dict for {vertex distmap} $graph {
dict set dist $vertex Inf
dict set path $vertex {}
}
dict set dist $origin 0
dict set path $origin [list $origin]
while {[dict size $graph]} {
# Find unhandled node with least weight
set d Inf
dict for {uu -} $graph {
if {$d > [set dd [dict get $dist $uu]]} {
set u $uu
set d $dd
}
}
# No such node; graph must be disconnected
if {$d == Inf} break
# Update the weights for nodes\
lead to by the node we've picked
dict for {v dd} [dict get $graph $u] {
if {[dict exists $graph $v]} {
set alt [expr {$d + $dd}]
if {$alt < [dict get $dist $v]} {
dict set dist $v $alt
dict set path $v [list {*}[dict get $path $u] $v]
}
}
}
# Remove chosen node from graph still to be handled
dict unset graph $u
}
return [list $dist $path]
}
Version data entries
17 entries across 17 versions & 1 rubygems