37 lines
1.5 KiB
Text
37 lines
1.5 KiB
Text
|
data cost <"1">, distance <"1">
|
|||
|
|
data vertex <'[a-f]'>, to <vertex>, from <vertex>, path <[<vertex>* VOID]>
|
|||
|
|
|
|||
|
|
templates shortestPaths&{graph:}
|
|||
|
|
@: {||};
|
|||
|
|
{| {to: $, distance: 0"1", path:[]} |} -> #
|
|||
|
|
when <?($::count <=0>)> do $@ !
|
|||
|
|
otherwise
|
|||
|
|
def closest: $ ... -> ..=Min&{by: :(distance:), select: :()};
|
|||
|
|
@: ($@ union {|$closest|});
|
|||
|
|
def path: [ $closest.path..., $closest.to ];
|
|||
|
|
{| ($ notMatching {| $closest({to:}) |})...,
|
|||
|
|
(($graph matching {| $closest({from: §.to}) |}) notMatching $@({to:}))...
|
|||
|
|
-> { to: $.to, distance: $.cost + $closest.distance, path: $path}
|
|||
|
|
|} -> #
|
|||
|
|
end shortestPaths
|
|||
|
|
|
|||
|
|
def edges: {|
|
|||
|
|
{ from: vertex´'a', to: vertex´'b', cost: 7"1" },
|
|||
|
|
{ from: vertex´'a', to: vertex´'c', cost: 9"1" },
|
|||
|
|
{ from: vertex´'a', to: vertex´'f', cost: 14"1" },
|
|||
|
|
{ from: vertex´'b', to: vertex´'c', cost: 10"1" },
|
|||
|
|
{ from: vertex´'b', to: vertex´'d', cost: 15"1" },
|
|||
|
|
{ from: vertex´'c', to: vertex´'d', cost: 11"1" },
|
|||
|
|
{ from: vertex´'c', to: vertex´'f', cost: 2"1" },
|
|||
|
|
{ from: vertex´'d', to: vertex´'e', cost: 6"1" },
|
|||
|
|
{ from: vertex´'e', to: vertex´'f', cost: 9"1" }
|
|||
|
|
|};
|
|||
|
|
|
|||
|
|
def fromA: vertex´'a' -> shortestPaths&{graph: $edges};
|
|||
|
|
|
|||
|
|
($fromA matching {|{to:vertex´'e'}|})... -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);
|
|||
|
|
' -> !OUT::write
|
|||
|
|
|
|||
|
|
($fromA matching {|{to:vertex´'f'}|})... -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);
|
|||
|
|
' -> !OUT::write
|