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: ⌊/⍬), 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 primitive operator @ to generate the new tree and cost vectors: new←back cvec decr⍨@wave¨⍵ ⍝ successor tree & cost 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 @ can be made to work if the links and costs are presented in _decreasing_ cost order: @(··D··D··D··)⊢ ·· C A B ·· ⍝ parent with link @(··D··D··D··)← ·· 13 12 11 ·· ⍝ updated cost vector. @ 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/¨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 ... 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←adjv I¨⊂cost ⍝ costs to beat mask←accm<best⌊to⊃cost ⍝ mask of better routes ¯¯¯¯¯¯¯¯ 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