## Description

FF - 2009-01-31 - Yeah! This is the season of graphs! :-)

This program is an animated demonstration of Dijkstra's algorithm for finding the minimum cost path (a.k.a. shortest path) in a cyclic graph.

See also Tcllib's package struct::graphop, a companion package to struct::graph which provides a number of graph algorithms, including Dijkstra.

## Changes

PYK 2012-12-04: removed update

## Code

```#! /bin/env tclsh

package require Tk
# Again, the procedures which add vertices and edges to canvas, and also in memory (array vertex, edge)

array set ::vertex {}
if {![info exists ::seq]} {set ::seq 0}
set ::vertex(\$::seq) [list \$x \$y]
set r 9
.c create oval \
[expr {\$x-\$r}] [expr {\$y-\$r}] \
[expr {\$x+\$r}] [expr {\$y+\$r}] \
-fill green -outline black \
-tags [list vertex vertex:\$::seq]
.c create text \$x \$y -text [expr {1+\$::seq}] \
-tags [list vertex_id vertex_id:\$::seq]
foreach tag [list vertex:\$::seq vertex_id:\$::seq] {
.c bind \$tag <ButtonPress-1> [list start \$::seq]
}
return [expr {[incr ::seq]-1}]
}

proc addEdge {a b {bidi 1} {weight auto}} {
array set ::edge {}
if {\$a == \$b} {return}
incr a -1 ; incr b -1
set dx [expr {[lindex \$::vertex(\$b) 0]-[lindex \$::vertex(\$a) 0]}]
set dy [expr {[lindex \$::vertex(\$b) 1]-[lindex \$::vertex(\$a) 1]}]
.c create line \
[lindex \$::vertex(\$a) 0] [lindex \$::vertex(\$a) 1] \
[lindex \$::vertex(\$b) 0] [lindex \$::vertex(\$b) 1] \
-width 1 -fill gray -tags [list edge edge:\$a:\$b]
.c raise vertex
.c raise vertex_id
if {\$weight eq "auto"} {
set weight [expr {hypot(\$dx,\$dy)}]
}
set ::edge(\$a:\$b) \$weight
if \$bidi {set ::edge(\$b:\$a) \$weight}
if {\$weight == 0} {return}
.c create text \
[expr {[lindex \$::vertex(\$a) 0]+\$dx/2}] \
[expr {[lindex \$::vertex(\$a) 1]+\$dy/2}] \
-text [expr {round(\$weight)}] -tags weight
}

set r {}
foreach v [array names ::edge \$v:*] {lappend r [lindex [split \$v :] 1]}
return \$r
}

proc done {} {
.c configure -cursor {}
set ::working 0
}

proc walk {} {
global T
set stop 1
foreach t \$T {if {[info exists ::cost(\$t)]} {set stop 0; break}}
if \$stop {done ;return}

foreach j \$T {
if {![info exists ::cost(\$j)]} {continue}
if {![info exists v_min] || \$::cost(\$j) <= \$::cost(\$v_min)} {
set v_min \$j
}
}
set cur \$v_min

lappend S \$v_min
set T [lreplace \$T [lsearch -exact \$T \$v_min] [lsearch -exact \$T \$v_min]]
if {[llength \$T] == 0} {done ;return}

if {[lsearch -exact \$T \$i] < 0} {continue}
if {![info exists ::cost(\$i)] || \$::cost(\$i) > [expr {\$::cost(\$v_min)+\$::edge(\$v_min:\$i)}]} {
set ::cost(\$i) [expr {\$::cost(\$v_min)+\$::edge(\$v_min:\$i)}]
set ::prev(\$i) \$v_min
}
}
after 500 after idle walk
}

# here's the algorithm itself

proc dijkstra {s} {
global T
set T [array names ::vertex]
set S [list]
array set ::cost {}
array set ::prev {}
set cur \$s

lappend S \$cur
set T [lreplace \$T [lsearch -exact \$T \$cur] [lsearch -exact \$T \$cur]]

set ::cost(\$v) \$::edge(\$cur:\$v)
set ::prev(\$v) \$cur
}

walk
}

# and the usual GUI stuff:

.c itemconfigure edge -width 1 -fill gray
.c delete cost
foreach v [array names ::prev] {
.c itemconfigure edge:\$v:\$::prev(\$v) -width 3 -fill red
.c itemconfigure edge:\$::prev(\$v):\$v -width 3 -fill red
.c create text \
[expr {[lindex \$::vertex(\$v) 0]+12}] \
[expr {[lindex \$::vertex(\$v) 1]-2}] \
-tags cost -fill red -text [expr {round(\$::cost(\$v))}] -anchor nw
}
}

proc start {v} {
catch {if \$::working return}
set ::working 1
.c itemconfigure vertex -fill green
.c itemconfigure vertex_id -fill black
.c itemconfigure edge -width 1 -fill gray
.c delete cost
array unset ::cost
array unset ::prev
.c itemconfigure vertex:\$v -fill black
.c itemconfigure vertex_id:\$v -fill white
.c configure -cursor watch
dijkstra \$v
}

pack [label .l -text "Click on a vertex to start Dijkstra's Shortest Path algorithm starting from there"]
canvas .c -width 600 -height 500 -background white

foreach {x y} {
20 100 180 120 260  70  80  30  60 180 170  60 180 190 290 150
370 200 420 110 300  10 410  30 510  80 300 240 120 260 490 190
580 150 530 270 400 280  20 270  85 350 205 320 300 320 400 340
540 350  30 430  95 470 190 415 350 450 490 415 570 460