Dijkstra Shortest Path
[1/3] from: rebol:optushome:au at: 27-Dec-2001 7:38
Hi all,
I was asked if there were any shortest path algorithms written in REBOL.
Particularly a "Dijkstra shortest path" example. Any takers?
Cheers,
Allen K
[2/3] from: tomc:darkwing:uoregon at: 1-Jan-2002 15:00
Hi Allen, couldn't resist.
rebol[title: "call dijk"]
; load/include a graph object and two functions, init-graph and dijk
do http://darkwing.uoregon.edu/~tomc/core/algo/dijk.r
; which will also include a heap from the same place
comment{
expects data as an edge-list with weights in file format:
node1 node2 weight1_2 newline
...
ex:
s u 10
s x 5
u v 1
u x 2
x u 3
x v 9
x y 2
v y 4
y v 6
y s 7
}
; read data into a graph
g: init-graph read/lines http://darkwing.uoregon.edu/~tomc/edge-list.txt
; pick a start node at random
start: pick g/nodes random (length? g/nodes)
;;; run Dijkstra's
dijk g start/id
; see what the shortest distance from the start to each node is
; also be able to recover the path by stepping to the previous node
print ["node-id distance previous-id"]
foreach n g/nodes[print[n/id tab n/distance tab n/previous/id]]
print ""
On Thu, 27 Dec 2001, Allen Kamp wrote:
[3/3] from: rebol:optushome:au at: 2-Jan-2002 10:42
Thanks Tom,
I'll pass it on.
Cheers,
Allen