Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|Tailspin}}: Update to stricter typing
Thundergnat (talk | contribs) m (→{{header|C sharp}}: Regularize header markup to recommended on category page) |
(→{{header|Tailspin}}: Update to stricter typing) |
||
Line 5,573:
A simple algorithm that traverses through all edges at every step.
<lang tailspin>
data
templates shortestPaths&{graph:}
@: [];
[ {to: $, distance: 0"1", path:[]} ] -> #
when <[](0)> do $@ !
otherwise
Line 5,589:
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
</lang>
Line 5,649:
{{out}}
<pre>
Shortest path from a to e is distance 26"1" via [c, d]
Shortest path from a to f is distance 11"1" via [c]
</pre>
| |||