wpath←{ ⍝ Quickest path fm/to ⍵ in weighted graph ⍺. graph costs←↓⍺ ⍝ graph structure and costs fm to←⍵ ⍝ start and ending vertices tree←¯1⊣¨graph ⍝ initial spanning tree cost←(⌊/⍬)×fm≠⍳⍴costs ⍝ cost to reach each vertex I←⊃¨∘⊂ ⍝ helper function: ⍺th items of ⍵ fm{ ⍝ from starting vertex. acc to←⍵ ⍝ accumulator and next vertex to<0:(to=¯2)↓acc ⍝ root or unvisited vertex: finished ⍺ ∇(to,acc)(to⊃⍺) ⍝ otherwise: parent vertex prefix }{ ⍝ lowest spanning cost tree: tree cost←⍵ ⍝ current tree and cost vectors ⍺≡⍬:tree ⍺⍺ ⍬ to ⍝ all vertices visited: done adjv←⍺ I graph ⍝ adjacent vertices accm←⍺ I cost+costs ⍝ costs to adjacent vertices best←adjv I¨⊂cost ⍝ costs to beat mask←accm<best⌊to⊃cost ⍝ mask of better routes next←mask/¨adjv ⍝ next vertices to visit back←⊃,/⍺+0×next ⍝ back links to parent nodes cvec←⊃,/mask/¨accm ⍝ cost vector decr←(⍒cvec)I⊢ ⍝ in decreasing order of cost wave←decr↑,/next ⍝ vertex wave front new←back cvec decr⍨@wave¨⍵ ⍝ successor tree & cost (∪wave)∇ new ⍝ wave spreads to adjacent vertices }tree cost ⍝ initial spanning tree and cost vectors } code_colours test script Back to: notes Back to: Workspaces