Dijkstra's algorithm: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 45:
;An example, starting with:
<syntaxhighlight lang="text"> a──►b, cost=7, lastNode=a
a──►c, cost=9, lastNode=a
a──►d, cost=NA, lastNode=a
Line 84:
c──►f
a──►c
a──►b ] </
Line 144:
{{trans|Python}}
<
String start
String end
Line 194:
(‘b’, ‘d’, 15), (‘c’, ‘d’, 11), (‘c’, ‘f’, 2), (‘d’, ‘e’, 6),
(‘e’, ‘f’, 9)])
print(graph.dijkstra(‘a’, ‘e’))</
{{out}}
Line 205:
This solution uses a generic package and Ada 2012 (containers, extended return statements, expression functions).
The very convenient 'Img attribute is a GNAT feature.
<
generic
type t_Vertex is (<>);
Line 236:
end record;
type t_Graph is array (t_Vertex) of t_Vertex_Data;
end Dijkstra;</
<
package body Dijkstra is
Line 328:
end Distance;
end Dijkstra;</
The testing main procedure :
<
with Dijkstra;
procedure Test_Dijkstra is
Line 368:
end loop;
end loop;
end Test_Dijkstra;</
{{out}}
<pre>Path from 'a' to 'e' = [a,c,d,e] distance = 26
Line 414:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
'''File: prelude_dijkstras_algorithm.a68'''<
COMMENT REQUIRED BY "prelude_dijkstras_algorithm.a68" CO
Line 554:
);
SKIP</
# -*- coding: utf-8 -*- #
Line 605:
# TODO: generate random 100000 VERTEX graph test case and test performance - important #
)</
<pre>
a --9-> c --2-> f --9-> e
Line 611:
=={{header|Applesoft BASIC}}==
<
110 DEF FN N(P) = ASC(MID$(N$,P+(P=0),1))-64
120 DIM D(26),UNVISITED(26)
Line 661:
670 DATA 6,D-E
680 DATA 9,E-F
690 DATA</
'''Output:'''
<pre>SHORTEST PATH
Line 674:
{{trans|Nim}}
<
initGraph: function [edges][
Line 745:
print ["Shortest path from 'a' to 'e': " join.with:" -> " dijkstraPath graph "a" "e"]
print ["Shortest path from 'a' to 'f': " join.with:" -> " dijkstraPath graph "a" "f"]</
{{out}}
Line 753:
=={{header|AutoHotkey}}==
<
nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
for each, line in StrSplit(data, "`n" , "`r")
Line 797:
count := A_Index
return count
}</
Examples:<
(
A B 7
Line 856:
GuiClose:
ExitApp
return</
Outputs:<pre>A > C 9
C > F 2
Line 865:
=={{header|C}}==
The priority queue is implemented as a binary heap. The heap stores an index into its data array, so it can quickly update the weight of an item already in it.
<syntaxhighlight lang="cafe">
#include <stdio.h>
#include <stdlib.h>
Line 1,046:
return 0;
}
</syntaxhighlight>
output
26 acde
Line 1,052:
=={{header|C sharp|C#}}==
{{works with|C sharp|7}}
<
using static System.String;
using static System.Console;
Line 1,189:
}
}</
{{out}}
<pre>
Line 1,212:
The outer loop executes once for each element popped from the priority queue, so it will execute at most once for each vertex, so at most V times. Each iteration of the outer loop executes one pop from the priority queue, which has time complexity O(log V). The inner loop executes at most once for each directed edge, since each directed edge has one originating vertex, and there is only at most one iteration of the outer loop for each vertex. Each iteration of the inner loop potentially performs one push or re-order on the priority queue (where re-order is a pop and a push), which has complexity O(log V). There is also the O(V) complexity for initializing the data structures. Combining these, we have a complexity of O(V log V + E log V), and assuming this is a connected graph, V <= E+1 = O(E), so we can write it as O(E log V).
<
#include <vector>
#include <string>
Line 1,332:
return 0;
}</
----
Line 1,346:
The number of times the outer loop executes (the number of times an element is popped from the priority queue) is bounded by E, and in each iteration, the popping operation takes time complexity O(log E). The number of times the inner loop executes is also bounded by E, and the pushing operation inside it also takes time complexity O(log E). So in total, the time complexity is O(E log E). But not that, for a simple graph, E < V^2, so log E < 2 log V = O(log V). So O(E log E) can also be written as O(E log V), which is the same as for the preceding algorithm.
<
#include <vector>
#include <string>
Line 1,473:
return 0;
}</
=={{header|CafeOBJ}}==
Dijkstra's algorithm repeatedly chooses the nearest vertex and relaxes the edges leaving it, terminating when no more vertices are accessible from the origin.
<syntaxhighlight lang="cafeobj">
"
This code works with CafeOBJ 1.5.1 and CafeOBJ 1.5.5.
Line 1,671:
-- 'a' :p 'c' :p 'f':PathList
eof
</syntaxhighlight>
=={{header|Clojure}}==
<
(declare neighbours
process-neighbour
Line 1,872:
;; | e | 26 | (a c d e) |
;; | f | 11 | (a c f) |
</syntaxhighlight>
=={{header|Commodore BASIC}}==
Line 1,879:
(The program outputs the shortest path to each node in the graph, including E and F, so I assume that meets the requirements of Task item 3.)
<
110 READ N$:IF N$<>"" THEN NV=NV+1:GOTO 110
120 NE=0: REM NUMBER OF EDGES
Line 1,941:
700 DATA 4,5,9
710 DATA -1
720 DATA 0</
{{Out}}
Line 1,955:
=={{header|Common Lisp}}==
<
(defparameter *w* '((a (a b . 7) (a c . 9) (a f . 14))
(b (b c . 10) (b d . 15))
Line 1,976:
(defun nodes (c)
(sort (cdr (assoc c *w*)) #'< :key #'cddr))
</syntaxhighlight>
{{out}}
<pre>
Line 1,982:
((A C D E) 26)
</pre>
<
(defvar *r* nil)
Line 1,999:
(paths w b g (+ (cddr a) z)
(cons b v))))))
</syntaxhighlight>
{{out}}
<pre>
Line 2,030:
{{trans|C++}}
The algorithm and the important data structures are essentially the same as in the C++ version, so the same comments apply (built-in D associative arrays are unsorted).
<
alias Vertex = string;
Line 2,112:
writeln(`Distance from "a" to "e": `, minDistance["e"]);
writeln("Path: ", dijkstraGetShortestPathTo("e", previous));
}</
{{out}}
<pre>Distance from "a" to "e": 26
Line 2,121:
An infinite distance is here represented by -1, which complicates the code when comparing distances, but ensures that infinity can't be equalled or exceeded by any finite distance.
<
{$APPTYPE CONSOLE}
Line 2,230:
WriteLn( lineOut);
end;
end.</
{{out}}
<pre>
Line 2,243:
=={{header|Emacs Lisp}}==
<
;; Path format: (start-point end-point previous-point distance)
(setq path-list `(
Line 2,337:
(calculate-shortest-path)
</syntaxhighlight>
outputs:
Line 2,353:
=={{header|Erlang}}==
<
-module(dijkstra).
-include_lib("eunit/include/eunit.hrl").
Line 2,400:
io:format(user, "The total cost was ~p and the path was: ", [Cost]),
io:format(user, "~w~n", [Path]).
</syntaxhighlight>
{{out}}
Line 2,415:
=={{header|F_Sharp|F#}}==
===Dijkstra's algorithm===
<
//Dijkstra's algorithm: Nigel Galloway, August 5th., 2018
[<CustomEquality;CustomComparison>]
Line 2,443:
|_ ->None
fN n [])
</syntaxhighlight>
===The Task===
<
type Node= |A|B|C|D|E|F
let G=Map[((A,B),7);((A,C),9);((A,F),14);((B,C),10);((B,D),15);((C,D),11);((C,F),2);((D,E),6);((E,F),9)]
Line 2,452:
printfn "%A" (paths E)
printfn "%A" (paths F)
</syntaxhighlight>
{{out}}
<pre>
Line 2,460:
=={{header|Go}}==
<
import (
Line 2,622:
fmt.Printf("Distance to %s: %d, Path: %s\n", "e", dist[g.ids["e"]], g.path(g.ids["e"], prev))
fmt.Printf("Distance to %s: %d, Path: %s\n", "f", dist[g.ids["f"]], g.path(g.ids["f"], prev))
}</
Runable on the [https://play.golang.org/p/w6nJ1ovjwn7 Go playground].
{{out}}
Line 2,634:
{{trans|C++}}
Translation of the C++ solution, and all the complexities are the same as in the C++ solution. In particular, we again use a self-balancing binary search tree (<code>Data.Set</code>) to implement the priority queue, which results in an optimal complexity.
<
{-# LANGUAGE FlexibleContexts #-}
import Data.Array
Line 2,692:
putStrLn $ "Distance from a to e: " ++ show (min_distance ! 'e')
let path = shortest_path_to 'e' ' ' previous
putStrLn $ "Path: " ++ show path</
=={{header|Huginn}}==
<
import Mathematics as math;
import Text as text;
Line 2,824:
print( "{}\n".format( g.path( paths, "e" ) ) );
print( "{}\n".format( g.path( paths, "f" ) ) );
}</
Sample run via: <pre>cat ~/graph.g | ./dijkstra.hgn</pre>, output:
Line 2,848:
discovered and then outputs the shortest path.
<
graph := getGraph()
repeat {
Line 2,956:
procedure waitForCompletion()
critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)
end</
Sample run:
Line 2,990:
=={{header|J}}==
<syntaxhighlight lang="j">
NB. verbs and adverb
parse_table=: ;:@:(LF&= [;._2 -.&CR)
Line 3,065:
5 3 9
)
</syntaxhighlight>
=== J: Alternative Implementation ===
<
edges=:|: ;:;._2]0 :0
a b 7
Line 3,111:
end.
best {L:0 _ m
)</
Example use:
<
┌─────────┐
│┌─┬─┬─┬─┐│
││a│c│d│e││
│└─┴─┴─┴─┘│
└─────────┘</
This version finds all shortest paths, and for this example completes in two thirds the time of the other J implementation.
Line 3,132:
Vertices are stored in a TreeSet (self-balancing binary search tree) instead of a PriorityQueue (a binary heap) in order to get O(log n) performance for removal of any element, not just the head.
Decreasing the distance of a vertex is accomplished by removing it from the tree and later re-inserting it.
<
import java.io.*;
import java.util.*;
Line 3,292:
}
}
}</
a -> c(9) -> d(20) -> e(26)
</pre>
Line 3,298:
=={{header|Javascript}}==
Using the [[wp:Dijkstra's_algorithm#Pseudocode]]
<
const dijkstra = (edges,source,target) => {
const Q = new Set(),
Line 3,384:
console.log(path) //[ 'a', 'c', 'f', 'e' ]
console.log(length) //20
</syntaxhighlight>
=={{header|jq}}==
Line 3,402:
'''Preliminaries'''
<
# def keys_unsorted: keys;
Line 3,471:
| readout($endname) ;
</syntaxhighlight>
'''The Task'''
<
"a": {"b": 7, "c": 9, "f": 14},
"b": {"c": 10, "d": 15},
Line 3,485:
"\nThe shortest paths from a to e and to f:",
(GRAPH | Dijkstra("a"; "e", "f") | .[0])</
{{out}}
<pre>
Line 3,497:
{{works with|Julia|0.6}}
<
edges::Dict{Tuple{U,U},T}
verts::Set{U}
Line 3,569:
path, cost = dijkstrapath(g, src, dst)
@printf("%4s | %3s | %s\n", src, dst, isempty(path) ? "no possible path" : join(path, " → ") * " ($cost)")
end</
{{out}}
Line 3,615:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.TreeSet
Line 3,761:
printPath(END)
}
}</
{{out}}
Line 3,772:
=={{header|Lua}}==
Hopefully the variable names here make the process as clear as possible...
<
local edges = {
a = {b = 7, c = 9, f = 14},
Line 3,838:
-- Main procedure
print("Directed:", dijkstra(edges, "a", "e", true))
print("Undirected:", dijkstra(edges, "a", "e", false))</
{{out}}
<pre>Directed: 26 a c d e
Line 3,844:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Dijkstra`s_algorithm {
const max_number=1.E+306
Line 3,932:
}
Dijkstra`s_algorithm
</syntaxhighlight>
{{out}}
Line 3,988:
=={{header|Maple}}==
<
with(GraphTheory):
G:=Digraph([a,b,c,d,e,f],{[[a,b],7],[[a,c],9],[[a,f],14],[[b,c],10],[[b,d],15],[[c,d],11],[[c,f],2],[[d,e],6],[[e,f],9]}):
DijkstrasAlgorithm(G,a);
# [[[a], 0], [[a, b], 7], [[a, c], 9], [[a, c, d], 20], [[a, c, d, e], 26], [[a, c, f], 11]]</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
"b" \[DirectedEdge] "c", "b" \[DirectedEdge] "d",
"c" \[DirectedEdge] "d", "d" \[DirectedEdge] "e",
Line 4,005:
FindShortestPath[bd, "a", "e", Method -> "Dijkstra"]
-> {"a", "c", "d", "e"}</
[[File:Mma_dijkstra2.PNG]]
=={{header|Maxima}}==
<
g: create_graph([[1, "a"], [2, "b"], [3, "c"], [4, "d"], [5, "e"], [6, "f"]],
[[[1, 2], 7],
Line 4,022:
shortest_weighted_path(1, 5, g);
/* [26, [1, 3, 4, 5]] */</
=={{header|Nim}}==
Translation of Wikipedia pseudo-code.
<syntaxhighlight lang="nim">
# Dijkstra algorithm.
Line 4,106:
printPath(graph.dijkstraPath("a", "e"))
printPath(graph.dijkstraPath("a", "f"))
</syntaxhighlight>
{{out}}
<pre>
Line 4,117:
Just a straightforward implementation of the pseudo-code from the Wikipedia article:
<
List.fold_left (fun acc ((a, b), _) ->
let acc = if List.mem b acc then acc else b::acc in
Line 4,203:
in
let p = dijkstra max_int 0 (+) graph "a" "e" in
print_endline (String.concat " -> " p)</
Output:
Line 4,211:
{{trans|C++}}
Translation of the C++ solution, and all the complexities are the same as in the C++ solution. In particular, we again use a self-balancing binary search tree (<code>Set</code>) to implement the priority queue, which results in an optimal complexity.
<
type weight = float
type neighbor = vertex * weight
Line 4,266:
print_string "Path: ";
List.iter (Printf.printf "%d, ") path;
print_newline ()</
=={{header|PARI/GP}}==
Basic, inefficient implementation. Takes an n×n matrix representing distance between nodes (a 0-1 matrix if you just want to count number of steps) and a number in 1..n representing the starting node, which defaults to 1 if not given.
<
my(n=#G[,1],dist=vector(n,i,9e99),prev=dist,Q=2^n-1);
dist[startAt]=0;
Line 4,288:
);
dist
};</
=={{header|Pascal}}==
Classic algorithm like this has to have a Pascal implementation...
<
type
Line 4,454:
vtx := vtx^.next;
end
end.</
{{Out}}
Line 4,475:
Almost every online description of the algorithm introduces the concept of infinite path length. There is no mention of this in Dijkstra's paper, and it doesn't seem to be necessary.
<
program Dijkstra_console;
// Demo of Dijkstra's algorithm.
Line 4,583:
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Line 4,595:
=={{header|Perl}}==
<
use warnings;
use constant True => 1;
Line 4,657:
}
my $path = join '', reverse @a;
print "$g->{e}{dist} $path\n";</
{{out}}
<pre>26 acde</pre>
Line 4,665:
Selects the shortest path from A to B only. As for time complexity, it looks plenty efficient enough to me, though it clearly is O(V^2).<br>
Written after the task was changed to be a directed graph, and shows the correct solution for that.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">--requires("1.0.2") -- (builtin E renamed as EULER)
Line 4,751:
<span style="color: #000000;">test</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">A</span><span style="color: #0000FF;">,</span><span style="color: #000000;">E</span><span style="color: #0000FF;">,</span><span style="color: #000000;">26</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ACDE"</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">A</span><span style="color: #0000FF;">,</span><span style="color: #000000;">F</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ACF"</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">F</span><span style="color: #0000FF;">,</span><span style="color: #000000;">A</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"none"</span><span style="color: #0000FF;">}})</span>
<!--</
{{out}}
<pre>
Line 4,761:
=={{header|PHP}}==
There are parts of this algorithm that could be optimized which have been marked TODO.
<syntaxhighlight lang="php">
<?php
function dijkstra($graph_array, $source, $target) {
Line 4,831:
echo "path is: ".implode(", ", $path)."\n";
</syntaxhighlight>
Output is:
<pre>path is: a, c, f, e</pre>
Line 4,837:
=={{header|PicoLisp}}==
Following the Wikipedia algorithm:
<
(push (prop X 'neighbors) (cons Y Cost))
(push (prop Y 'neighbors) (cons X Cost)) )
Line 4,854:
(del (asoq Curr (: neighbors)) (:: neighbors)) ) )
(setq Curr Next Cost Min) ) )
Cost ) )</
Test:
<
(neighbor 'a 'c 9)
(neighbor 'a 'f 14)
Line 4,866:
(neighbor 'e 'f 9)
(dijkstra 'a 'e)</
Output:
<pre>-> 20</pre>
Line 4,915:
<
:-dynamic
Line 4,961:
[Path, Dist, Distance]);
writef('There is no route from %w to %w\n', [From, To]).
</syntaxhighlight>
for example:
<pre>?- go(a,e).
Line 4,984:
Note: q could be changed to be a priority queue instead of a set as mentioned [http://docs.python.org/3.3/library/heapq.html#priority-queue-implementation-notes here].
<
from pprint import pprint as pp
Line 5,033:
("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),
("e", "f", 9)])
pp(graph.dijkstra("a", "e"))</
{{out}}
Line 5,039:
=={{header|Racket}}==
<
#lang racket
(require (planet jaymccarthy/dijkstra:1:2))
Line 5,062:
(cond [(eq? (first path) 'a) path]
[(loop (cons (hash-ref prevs (first path)) path))]))))])
</syntaxhighlight>
Output:
<
Distances from a: ((b 7) (d 20) (a 0) (c 9) (f 11) (e 26))
Shortest path: (a c d e)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|Rakudo|2018.03}}
<syntaxhighlight lang="raku"
has (%.edges, %.nodes);
Line 5,151:
["d", "e", 6],
["e", "f", 9]
]).dijkstra('a', 'e').say;</
{{out}}
<pre>
Line 5,162:
:::* a test for a ''no path found'' condition
:::* use of memoization
<
$.= copies(9, digits() ) /*edge cost: indicates doesn't exist. */
xList= '!. @. $. beg fin bestP best$ xx yy' /*common EXPOSEd variables for subs. */
Line 5,217:
@.?= !.qq; call .path ?+1 /*recursive call for next path. */
end /*qq*/
return</
{{out|output|text= when using the internal default inputs:}}
<pre>
Line 5,237:
=={{header|Ring}}==
<
# Project : Dijkstra's algorithm
Line 5,315:
dgraph[p] = s
next
</syntaxhighlight>
Output:
<pre>
Line 5,327:
Notes for this solution:
* At every iteration, the next minimum distance node found by linear traversal of all nodes, which is inefficient.
<
Vertex = Struct.new(:name, :neighbours, :dist, :prev)
Line 5,397:
path, dist = g.shortest_path(start, stop)
puts "shortest path from #{start} to #{stop} has cost #{dist}:"
puts path.join(" -> ")</
{{out}}
Line 5,406:
This solution uses a very bare-bones, naive implementation of an adjacency list to represent the graph.
<
use std::collections::BinaryHeap;
use std::usize;
Line 5,524:
println!("\nCost: {}", cost);
}</
{{out}}
<pre>
Line 5,533:
=={{header|SAS}}==
Use network solver in SAS/OR:
<
data Edges;
input Start $ End $ Cost;
Line 5,570:
/* print shortest path */
proc print data=path;
run;</
Output:
Line 5,583:
A functional implementation of Dijkstras Algorithm:
<
type Path[Key] = (Double, List[Key])
Line 5,611:
println(res)
}
}</
{{out}}
Line 5,619:
An implementation based on the functional version above that uses <code>PriorityQueue</code>. It is made functional-look:
<
import scala.collection.mutable
Line 5,677:
}
}
</syntaxhighlight>
{{out}}
<pre>(26.0,List(a, c, d, e))</pre>
Line 5,683:
=={{header|Sidef}}==
{{trans|Perl}}
<
struct Node {
Line 5,773:
var path = a.reverse.join
say "#{g.get('e').dist} #{path}"</
{{out}}
<pre>
Line 5,785:
{{trans|Rust}}
<
struct Grid<T> {
Line 5,873:
print("Cost: \(cost)")
print(path.map({ grid.nodes[$0].data }).joined(separator: " -> "))</
{{out}}
Line 5,882:
=={{header|Tailspin}}==
A simple algorithm that traverses through all edges at every step.
<
data vertex <'a'..'f'>, to <vertex>
Line 5,916:
$fromA... -> \(<{to:<=vertex´'f'>}> $!\) -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);
' -> !OUT::write
</syntaxhighlight>
Alternatively you can use relational algebra operators for the exact same algorithm
<
data cost <"1">, distance <"1">
data vertex <'[a-f]'>, to <vertex>, from <vertex>, path <[<vertex>* VOID]>
Line 5,956:
($fromA matching {|{to:'f'}|})... -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 5,972:
Note that this code traverses the entire set of unrouted nodes at each step, as this is simpler than computing the subset that are reachable at each stage.
<
# Initialize
dict for {vertex distmap} $graph {
Line 6,009:
}
return [list $dist $path]
}</
Showing the code in use:
<
# Assume that all nodes are connected to something
foreach arc $arcs {
Line 6,026:
lassign [dijkstra [makeUndirectedGraph $arcs] "a"] costs path
puts "path from a to e costs [dict get $costs e]"
puts "route from a to e is: [join [dict get $path e] { -> }]"</
Output:
<pre>
Line 6,034:
=={{header|VBA}}==
<
Public from As Node '[according to Dijkstra the first Node should be closest to P]
Public towards As Node
Line 6,208:
Dijkstra testNodes, testBranches, a
GetPath f
End Sub</
a e 26 a c d e
a f 11 a c f</pre>
Line 6,218:
{{libheader|Wren-sort}}
{{libheader|Wren-set}}
<
import "/trait" for Comparable
import "/sort" for Cmp, Sort
Line 6,369:
g = Graph.new(GRAPH, false, false) // undirected
g.dijkstra(START)
g.printPath(END)</
{{out}}
Line 6,379:
=={{header|zkl}}==
<
fcn dijkstra(graph,start,dst){
Q :=graph.copy();
Line 6,400:
}
}
}</
<
"a", T(T("b", 7.0), T("c", 9.0), T("f",14.0)),
"b", T(T("c",10.0), T("d",15.0)),
Line 6,410:
);
dijkstra(graph,"a","e").println();
dijkstra(graph,"e","a").println();</
{{out}}
<pre>
|