34 lines
1.4 KiB
Text
34 lines
1.4 KiB
Text
|
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
|