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
        bestadjv I¨⊂cost           ⍝ costs to beat
        maskaccm<besttocost      ⍝ mask of better routes
        nextmaskadjv             ⍝ next vertices to visit
        back←⊃,/⍺+0×next            ⍝ back links to parent nodes
        cvec←⊃,/maskaccm          ⍝ cost vector
        decr(cvec)I⊢              ⍝ in decreasing order of cost
        wavedecr↑,/next            ⍝ vertex wave front
        newback cvec decr⍨@wave¨⍵  ⍝ successor tree & cost
        (wave)new                ⍝ wave spreads to adjacent vertices
    }tree cost                      ⍝ initial spanning tree and cost vectors

test script

Back to: notes

Back to: Workspaces