path ← wgraph ##.wpath (from to) ⍝ Quickest path from/to ⍵ in weighted graph ⍺.

[wgraph] is a 2-row matrix representing a weighted graph. The result [path] is a
vector  that  represents  a  lowest-cost path between the given vertices. Notice
that the return path (to from) may not be the reverse of the forward path.

NB:  All  of the weights in the 2nd row of [wgraph] must be non-negative, other-
wise the result is unpredictable.

Technical notes:

Shortest  paths  through  _unweighted_  graphs, result immediately from a simple
breadth-first  search:  the  target  vertex is discovered in the fewest possible
steps, as the search radiates outwards from the starting vertex.

However,  with  a _weighted_ graph, the search can't stop on finding the target,
as  there may yet be lower-cost paths. The technique used here, is to maintain a
cost-to-reach  value  (which  is initialised to: ⌊/⍳0), for each vertex. At each
point  in  the  search,  vertices  are pursued only if the cost of reaching them
would be less than their current cost-to-reach value. In this case, the cost-to-
reach value for the vertices is adjusted accordingly and the search continued.

As  the  "wave" front of visited vertices radiates from the starting vertex, the
code uses a destructive partial assignment to update tree and cost vectors:

        tree[wave]← ...         ⍝ link tree nodes to parent.
        cost[wave]← ...         ⍝ update cost vector.

A  problem arises if the wave converges on the same vertex from two or more dir-
ections.  The  following  diagram  shows the wave propogating left-to-right from
vertices A, B and C with cost-to-reach values of 8 9 and 7, respectively.

        A[8]───4──→─┐
                    │
        B[9]───2──→─D[?]
                    │
        C[7]───6──→─┘

The  edge  costs  A→D, B→D and C→D are 4 2 and 6, so the cost-to-reach D must be
set to:
            ⌊8 9 7+4 2 6
        11

The  partial  assignment can be made "just to work" if we assign links and costs
in _decreasing_ cost order:

        tree[··D··D··D··] ←  ··  C  A  B ·· ⍝ link tree nodes to parent.
        cost[··D··D··D··] ←  ·· 13 12 11 ·· ⍝ update cost vector.

APL's  indexed assignment is defined to process its subscripts left-to-right, so
that the right-most assignment to D is the only effective one. Here is the code:

        ...
        cvec←↑,/mask/¨totl          ⍝ cost vector.
        decr←⍒cvec                  ⍝ decreasing cost order.
        wave←decr⊃¨⊂↑,/next         ⍝ vertex wave front.
        tree[wave]←decr⊃¨⊂back      ⍝ link tree nodes to parent.
        cost[wave]←decr⊃¨⊂cvec      ⍝ update cost vector.
        ...
(
    ⍺⊃¨⊂⍵  is recognised as an idiom and is marginally quicker than the equival-
    ent ⍵[⍺].
)

Thanks to Mike Day for suggesting a fix to the original coding.

A small but important refinement, is to keep track of the cost-to-reach value of
the _target_ node. Any path that would be more expensive than this is ignored:

        best←(vals¨adjv)⌊to⊃cost    ⍝ costs to beat.

See also →bfs← for notes on parallel breadth-first search.

Examples:

    aa                      ⍝ weighted graph "aa"
┌───┬─┬───┬───┬─┐
│2 3│3│2 4│1 5│3│
├───┼─┼───┼───┼─┤
│1 3│1│4 1│1 1│1│
└───┴─┴───┴───┴─┘

    aa wpath 3 2            ⍝ best path 3→2.
3 4 1 2

    aa[1;] path 3 2         ⍝ compare: best path 3→2 _ignoring_ weights.
3 2

See also: wGraphs Graphs bfs wspan wcost path

Back to: contents

Back to: Workspaces