Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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