37 lines
1.5 KiB
Plaintext
37 lines
1.5 KiB
Plaintext
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
|