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