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
        maskaccm<adjv I¨⊂cost      ⍝ mask of better routes
        cvec←⊃,/maskaccm          ⍝ cost vector
        nextmaskadjv             ⍝ next vertices to visit
        back←⊃,/⍺+0×next            ⍝ back links to parent node
        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