Anonymous user
Dijkstra's algorithm: Difference between revisions
add Tailspin solution
(→{{header|Tcl}}: promoted an "incorrect" comment into a true "incorrect" flag, the original author of the comment is unknown at this time.) |
(add Tailspin solution) |
||
Line 4,434:
<pre>
26 acde
</pre>
=={{header|Tailspin}}==
A simple algorithm that traverses through all edges at every step.
<lang tailspin>
templates shortestPaths@{graph:}
@: [];
[ {to: $, distance: 0, path:[]} ] -> #
<[](0)> $@ !
<>
def closest: $ -> (@: $(1); $(2..-1)... -> # $@! <?($.distance <..~$@.distance>)> @: $;);
$closest -> ..|@: $;
def path: [ $closest.path..., $closest.to ];
[ $... -> (<?($.to <~$closest.to>)> $!),
$graph... -> (def to: $.edge(2); $ -> #
<?($.edge(1) <$closest.to>) ?($@shortestPaths <~[<{to: <$to>}>]>)> $!)
-> { to: $.edge(2), distance: $.cost + $closest.distance, path: $path} ] -> #
end shortestPaths
def edges: [
{ edge: ['a', 'b'], cost: 7 },
{ edge: ['a', 'c'], cost: 9 },
{ edge: ['a', 'f'], cost: 14 },
{ edge: ['b', 'c'], cost: 10 },
{ edge: ['b', 'd'], cost: 15 },
{ edge: ['c', 'd'], cost: 11 },
{ edge: ['c', 'f'], cost: 2 },
{ edge: ['d', 'e'], cost: 6 },
{ edge: ['e', 'f'], cost: 9 }];
def fromA: 'a' -> shortestPaths@{graph: $edges};
$fromA... -> (<{to:<'e'>}> $!) -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..-1);
' -> !OUT::write
$fromA... -> (<{to:<'f'>}> $!) -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..-1);
' -> !OUT::write
</lang>
{{out}}
<pre>
Shortest path from a to e is distance 26 via [c, d]
Shortest path from a to f is distance 11 via [c]
</pre>
| |||