wspan←{                             ⍝ Spanning tree for weighted graph ⍺ from ⍵.
    graph costs←↓⍺                  ⍝ graph structure and costs.
    tree←¯1⊣¨graph                  ⍝ initial spanning tree.
    cost←(⌊/⍬)×⍵≠⍳⍴costs            ⍝ cost to reach each vertex.
    I←⊃¨∘⊂                          ⍝ helper function: ⍺th items of ⍵
    ⍵{                              ⍝ from starting vertex.
        tree cost←⍵                 ⍝ current tree and costs
        ⍺≡⍬:tree                    ⍝ all vertices visited: done
        adjv←⍺ I graph              ⍝ adjacent vertices
        accm←⍺ I cost+costs         ⍝ cumulative cost via this vertex
        mask←accm<adjv I¨⊂cost      ⍝ mask of better routes
        cvec←⊃,/mask/¨accm          ⍝ cost vector
        next←mask/¨adjv             ⍝ next vertices to visit
        back←⊃,/⍺+0×next            ⍝ back links to parent node
        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