Dijkstra's algorithm: Difference between revisions
m
→{{header|EasyLang}}
m (→{{header|ATS}}) |
|||
| (26 intermediate revisions by 13 users not shown) | |||
Line 608:
<pre>
a --9-> c --2-> f --9-> e
</pre>
=={{header|Arturo}}==
{{trans|Nim}}
<syntaxhighlight lang="arturo">define :graph [vertices, neighbours][]
initGraph: function [edges][
Line 755 ⟶ 693:
This implementation is based on suggestions from
[https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1117533081#Using_a_priority_queue a Wikipedia article about Dijkstra's algorithm], although I use a different method to determine whether a queue entry is obsolete.
I prove that the algorithm terminates and that the priority queue has at least enough storage. The priority queue is a binary heap implemented as an array.
<syntaxhighlight lang="ats">
Line 782 ⟶ 720:
macdef infinity = $extval (flt, "INFINITY")
prfn
mul_compare_lte
{i, j, n : nat | i <= j}
:<prf> [i * n <= j * n] void =
mul_gte_gte_gte {j - i, n} ()
prfn
mul_compare_lt
{
()
:<
mul_compare_lte {i + 1, j, n} ()
(*------------------------------------------------------------------*)
Line 1,006 ⟶ 850:
fn
fprint_vertex_path
{n : int}
(outf : FILEref,
vertex_arr : arrayref (string, n),
path : List ([i : nat | i < n] size_t i)
cost_opt : Option flt,
cost_column_no : size_t)
: void =
let
Line 1,015 ⟶ 861:
loop {m : nat}
.<m>.
(path : list ([i : nat | i < n] size_t i, m)
: size_t =
case+ path of
| NIL =>
| i :: NIL =>
begin
fprint! (outf, vertex_arr[i]);
column_no + strlen vertex_arr[i]
end
| i :: tail =>
begin
fprint! (outf, vertex_arr[i], " -> ");
loop (tail, column_no + strlen vertex_arr[i] + i2sz 4)
end
prval () = lemma_list_param path
val column_no = loop (path, i2sz 1)
in
| None () => ()
| Some cost =>
let
var i : size_t = column_no
in
while (i < cost_column_no)
begin
fprint! (outf, " ");
i := succ i
end;
fprint! (outf, "(cost = ", cost, ")")
end
end
(*------------------------------------------------------------------*)
(* A binary-heap priority queue, similar to the Pascal in Robert
Sedgewick, "Algorithms", 2nd ed. (reprinted with corrections),
1989. Note that Sedgewick does an extract-max, whereas we do an
extract-min.
Niklaus Wirth, within the heapsort implementation of "Algorithms +
Data Structures = Programs", has, I will note, some Pascal code
that is practically the same as Sedgewick's. Can we trace that code
back farther to Algol?
We do not have "goto" for Sedgewick's "downheap" (or Wirth's
"sift"), but do have mutual tail call as an obvious alternative to
the "goto". Nevertheless, because the code "jumped to" is small, I
simply use a macro to duplicate it. *)
dataprop PQUEUE_N_MAX (n_max : int) =
| {0 <= n_max}
PQUEUE_N_MAX (n_max)
typedef pqueue (priority_t : t@ype+,
value_t : t@ype+,
n : int,
n_max : int) =
[n <= n_max]
@{
(* An earlier version of this structure stored a copy of n_max,
but the following use of the PQUEUE_N_MAX prop eliminates the
need for that. Instead the information is kept only at
typechecking time. *)
pf = PQUEUE_N_MAX (n_max) |
arr = arrayref (@(priority_t, value_t), n_max + 1),
n = size_t n
}
prfn
lemma_pqueue_param
{n_max : int}
{n : int}
{priority_t, value_t : t@ype}
(pq : pqueue (priority_t, value_t, n, n_max))
:<prf> [0 <= n; n <= n_max] void =
lemma_g1uint_param (pq.n)
extern praxi
lemma_pqueue_size
{n_max : int}
{n : int}
{priority_t, value_t : t@ype}
(pq : pqueue (priority_t, value_t, n, n_max))
:<prf> [n1 : int | n1 == n] void
extern fn {priority_t : t@ype}
pqueue$cmp :
(priority_t, priority_t) -<> int
extern fn {priority_t : t@ype}
pqueue$priority_min :
() -<> priority_t
implement pqueue$cmp<double> (x, y) = compare (x, y)
implement pqueue$priority_min<double> () = neg infinity
fn {priority_t : t@ype}
{value_t : t@ype}
pqueue_make_empty
{n_max : int}
(n_max : size_t n_max,
arbitrary_entry : @(priority_t, value_t))
:<!wrt> pqueue (priority_t, value_t, 0, n_max) =
let
(* Currently an array is allocated whose size is the proven
bound. It might be better to use a smaller array and allow
reallocation up to this maximum size, or to break the array
into pieces. *)
prval () = lemma_g1uint_param n_max
val arr =
arrayref_make_elt<@(priority_t, value_t)>
(succ n_max, arbitrary_entry)
in
@{pf = PQUEUE_N_MAX {n_max} () |
arr = arr,
n = i2sz 0}
end
fn {}
pqueue_clear
{n_max : int}
{n : int}
{priority_t : t@ype}
{value_t : t@ype}
(pq : &pqueue (priority_t, value_t, n, n_max)
>> pqueue (priority_t, value_t, 0, n_max))
:<!wrt> void =
let
prval PQUEUE_N_MAX () = pq.pf (* Proves 0 <= n_max. *)
in
pq := @{pf = pq.pf |
arr = pq.arr,
n = i2sz 0}
end
fn {}
pqueue_is_empty
{n_max : int}
{n : int}
{priority_t : t@ype}
{value_t : t@ype}
(pq : pqueue (priority_t, value_t, n, n_max))
:<> bool (n == 0) =
(pq.n) = i2sz 0
fn {}
pqueue_size
{n_max : int}
{n : int}
{priority_t : t@ype}
{value_t : t@ype}
(pq : pqueue (priority_t, value_t, n, n_max))
:<> size_t n =
pq.n
fn {priority_t : t@ype}
{value_t : t@ype}
_upheap {n_max : pos}
{n : int | n <= n_max}
{k0 : nat | k0 <= n}
(arr : arrayref (@(priority_t, value_t), n_max + 1),
k0 : size_t k0)
:<!refwrt> void =
let
macdef lt (x, y) = (pqueue$cmp<priority_t> (,(x), ,(y)) < 0)
macdef prio x = ,(x).0
val entry = arr[k0]
fun
loop {k : nat | k <= n}
.<k>.
(k : size_t k)
:<!refwrt> void =
if k = i2sz 0 then
arr[k] := entry
else
let
val kh = half k
in
if (prio entry) \lt (prio arr[kh]) then
begin
arr[k] := arr[kh];
loop kh
end
else
arr[k] := entry
end
in
arr[0] := @(pqueue$priority_min<priority_t> (), arr[0].1);
loop k0
end
fn {priority_t : t@ype}
{value_t : t@ype}
pqueue_insert
{n_max : int}
{n : int | n < n_max}
(pq : &pqueue (priority_t, value_t, n, n_max)
>> pqueue (priority_t, value_t, n + 1, n_max),
entry : @(priority_t, value_t))
:<!refwrt> void =
let
prval () = lemma_g1uint_param (pq.n)
val arr = pq.arr
and n1 = succ (pq.n)
in
arr[n1] := entry;
_upheap {n_max} {n + 1} (arr, n1);
pq := @{pf = pq.pf |
arr = arr,
n = n1}
end
fn {priority_t : t@ype}
{value_t : t@ype}
_downheap {n_max : pos}
{n : pos | n <= n_max}
(arr : arrayref (@(priority_t, value_t), n_max + 1),
n : size_t n)
:<!refwrt> void =
let
macdef lt (x, y) = (pqueue$cmp<priority_t> (,(x), ,(y)) < 0)
macdef prio x = ,(x).0
val entry = arr[1]
and nh = half n
fun
loop {k : pos | k <= n}
.<n - k>.
(k : size_t k)
:<!refwrt> void =
let
macdef move_data i =
if (prio entry) \lt (prio arr[,(i)]) then
arr[k] := entry
else
begin
arr[k] := arr[,(i)];
loop ,(i)
end
in
if nh < k then
arr[k] := entry
else
let
stadef j = 2 * k
prval () = prop_verify {j <= n} ()
val j : size_t j = k + k
in
if j < n then
let
stadef j1 = j + 1
prval () = prop_verify {j1 <= n} ()
val j1 : size_t j1 = succ j
in
if ~((prio arr[j]) \lt (prio arr[j1])) then
move_data j1
else
move_data j
end
else
move_data j
end
end
in
loop (i2sz 1)
end
fn {priority_t : t@ype}
{value_t : t@ype}
pqueue_peek
{n_max : int}
{n : pos | n <= n_max}
(pq : pqueue (priority_t, value_t, n, n_max))
:<!ref> @(priority_t, value_t) =
let
val arr = pq.arr
in
arr[1]
end
fn {priority_t : t@ype}
{value_t : t@ype}
pqueue_delete
{n_max : int}
{n : pos | n <= n_max}
(pq : &pqueue (priority_t, value_t, n, n_max)
>> pqueue (priority_t, value_t, n - 1, n_max))
:<!refwrt> void =
let
val @{pf = pf |
arr = arr,
n = n} = pq
in
if i2sz 0 < pred n then
begin
arr[1] := arr[n];
_downheap {n_max} {n - 1} (arr, pred n)
end;
pq := @{pf = pf |
arr = arr,
n = pred n}
end
fn {priority_t : t@ype}
{value_t : t@ype}
pqueue_extract
{n_max : int}
{n : pos | n <= n_max}
(pq : &pqueue (priority_t, value_t, n, n_max)
>> pqueue (priority_t, value_t, n - 1, n_max))
:<!refwrt> @(priority_t, value_t) =
let
val retval = pqueue_peek<priority_t><value_t> {n_max} {n} pq
in
pqueue_delete<priority_t><value_t> {n_max} {n} pq;
retval
end
local (* A little unit testing of the priority queue
implementation. *)
#define NMAX 10
in
var pq = pqueue_make_empty<double><int> (i2sz NMAX, @(0.0, 0))
val- true = pqueue_is_empty pq
val- true = (pqueue_size pq = i2sz 0)
val () = pqueue_insert (pq, @(3.0, 3))
val () = pqueue_insert (pq, @(5.0, 5))
val () = pqueue_insert (pq, @(1.0, 1))
val () = pqueue_insert (pq, @(2.0, 2))
val () = pqueue_insert (pq, @(4.0, 4))
val- false = pqueue_is_empty pq
val- true = (pqueue_size pq = i2sz 5)
val- @(1.0, 1) = pqueue_extract<double> pq
val- @(2.0, 2) = pqueue_extract<double> pq
val- @(3.0, 3) = pqueue_extract<double> pq
val- @(4.0, 4) = pqueue_extract<double> pq
val- @(5.0, 5) = pqueue_extract<double> pq
val- true = pqueue_is_empty pq
val- true = (pqueue_size pq = i2sz 0)
end
(*------------------------------------------------------------------*)
Line 1,050 ⟶ 1,226:
typedef defined_index_t = [i : nat | i < n] size_t i
val index_t_undefined : size_t n = n
val arbitrary_pq_entry : @(flt, defined_index_t) =
@(0.0, i2sz 0)
val prev = arrayref_make_elt<index_t> (n, index_t_undefined)
and cost = arrayref_make_elt<flt> (n, infinity)
val () = cost[source] := zero
(* The priority queue never gets larger than m_max. There is code
below that proves this; thus there is no risk of overrunning
the queue's storage (unless the queue implementation itself is
made unsafe). FIXME: Is it possible to prove a tighter bound on
the size of the priority queue? *)
stadef m_max = (n * n) + n + n
prval () = mul_pos_pos_pos (mul_make {n, n} ())
prval () = prop_verify {n + n < m_max} ()
val m_max : size_t m_max = (n * n) + n + n
typedef pqueue_t (m : int) =
[0 <= m
pqueue (flt, defined_index_t, m, m_max)
typedef pqueue_t =
[m : int] pqueue_t m
fn
pq_make_empty ()
:<!wrt> pqueue_t 0 =
(* Create a priority queue, whose maximum size is our proven
upper bound on the queue size. *)
pqueue_make_empty<flt><defined_index_t>
(m_max, arbitrary_pq_entry)
var pq = pq_make_empty ()
val active = arrayref_make_elt<bool> (n, true)
var num_active : [i : nat | i <= n] size_t i = n
fun
fill_pq {i : nat | i <= n}
.<n - i>.
(pq : &pqueue_t i >>
i : size_t i)
:<!refwrt> void =
if i <> n then
begin
pqueue_insert {m_max} {i} (pq, @(cost[i], i));
fill_pq {i + 1} (pq, succ i)
end
fun
extract_min
:<!refwrt>
@(flt, defined_index_t) =
let
val @(priority, vertex) =
pqueue_extract<flt><defined_index_t> {m_max} {m0} pq
in
if active[vertex] then
@(priority, vertex)
else if pqueue_is_empty {m_max} pq then
arbitrary_pq_entry
else
extract_min pq
end
fun
main_loop {num_active0 : nat | num_active0 <= n}
{qsize0 : nat}
{qlimit0 : int | 0 <= qlimit0;
qsize0 <= qlimit0 + n}
.<num_active0>.
(* The pf_qlimit0 prop helps us prove a bound on the
size of the priority queue. We need it because the
proof capabilities built into ATS have very limited
ability to handle multiplication. *)
(pf_qlimit0 : MUL (n - num_active0, n, qlimit0) |
pq : &pqueue_t qsize0 >> pqueue_t 0,
num_active : &size_t num_active0 >> size_t num_active1)
:<!refwrt> #[num_active1 : nat | num_active1 <= num_active0]
void =
if num_active = i2sz 0 then
pqueue_clear pq
else if pqueue_is_empty {m_max} {qsize0} pq then
let (* This should not happen. *)
val- false = true
in
end
else
let
prval () =
prop_verify {qsize0 <= ((n - num_active0) * n) + n} ()
prval () = mul_compare_lt {n - num_active0, n, n} ()
prval () = prop_verify {qsize0 < m_max} ()
val @(priority, u) = extract_min pq
prval [qsize : int] () = lemma_pqueue_size {m_max} pq
prval () = lemma_pqueue_param {m_max} {qsize} pq
prval () = prop_verify {qsize < qsize0} ()
prval () = prop_verify {qsize < m_max} ()
val () = active[u] := false
and () = num_active := pred num_active
.<n -
(pq : &pqueue_t m0
v
:<!refwrt> #[m1 : int | qsize <= m1; m1 <= qsize
loop_over_vertices {v + 1}
let
val alternative = cost[u] + adj_matrix[u, n, v]
in
if alternative < cost[v] then
let
in
prev[v] :=
are obsolete if the
"active"
(pq, @(alternative, v));
loop_over_vertices {v + 1} {m0 + 1}
(pq, succ v)
end
end
in
main_loop {num_active0 - 1}
(MULind pf_qlimit0 | pq, num_active)
end
in
fill_pq {0} (pq, i2sz 0);
main_loop {n} {n} (MULbas () | pq, num_active);
@(cost, prev)
end
Line 1,200 ⟶ 1,452:
val- Some path_a_to_e = least_cost_path {n} (a, prev, n, e)
val- Some path_a_to_f = least_cost_path {n} (a, prev, n, f)
var u : [i : nat | i <= n] size_t i
val cost_column_no = i2sz 20
in
println! ("The requested paths:");
fprint_vertex_path (stdout_ref, vertex_arr, path_a_to_e,
Some cost[e], cost_column_no);
println! (
fprint_vertex_path (stdout_ref, vertex_arr, path_a_to_f,
Some cost[f], cost_column_no);
println! ();
println! ();
println! ("All paths (in no particular order):");
for (u := i2sz 0; u <> n; u := succ u)
case+ least_cost_path {n} (a, prev, n, u) of
| None () =>
println! ("There is no path from ", vertex_arr[a], " to ",
vertex_arr[u], ".")
| Some path =>
begin
fprint_vertex_path (stdout_ref, vertex_arr, path,
Some cost[u], cost_column_no);
println! ()
end
end
Line 1,211 ⟶ 1,482:
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW dijkstra-algorithm.dats -lgc && ./a.out
The requested paths:
a -> c ->
a -> c -> f (cost = 11.000000)
All paths (in no particular order):
a -> c -> d -> e (cost = 26.000000)
a -> c -> d (cost = 20.000000)
a -> c -> f (cost = 11.000000)
a -> c (cost = 9.000000)
a -> b (cost = 7.000000)
a (cost = 0.000000)
</pre>
=={{header|AutoHotkey}}==
Line 1,324 ⟶ 1,605:
F > E 9
Total distance = 20</pre>
=={{header|AWK}}==
A very basic implementation in AWK. Minimum element in the queue is found by a linear search.
<syntaxhighlight lang="awk">
NF == 3 { graph[$1,$2] = $3 }
NF == 2 {
weight = shortest($1, $2)
n = length(path)
p = $1
for (i = 2; i < n; i++)
p = p "-" path[i]
print p "-" $2 " (" weight ")"
}
# Edge weights are in graph[node1,node2]
# Returns the weight of the shortest path
# Shortest path is in path[1] ... path[n]
function shortest(from, to, queue, q, dist, v, i, min, edge, e, prev, n) {
delete path
dist[from] = 0
queue[q=1] = from
while (q > 0) {
min = 1
for (i = 2; i <= q; i++)
if (dist[queue[i]] < dist[queue[min]])
min = i
v = queue[min]
queue[min] = queue[q--]
if (v == to)
break
for (edge in graph) {
split(edge, e, SUBSEP)
if (e[1] != v)
continue
if (!(e[2] in dist) || dist[e[1]] + graph[edge] < dist[e[2]]) {
dist[e[2]] = dist[e[1]] + graph[edge]
prev[e[2]] = e[1]
queue[++q] = e[2]
}
}
}
if (v != to)
return "n/a"
# Build the path
n = 1
for (v = to; v != from; v = prev[v])
n++
for (v = to; n > 0; v = prev[v])
path[n--] = v
return dist[to]
}
</syntaxhighlight>
Example:
<syntaxhighlight lang="bash">
$ cat dijkstra.txt
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
a e
a f
f a
$ awk -f dijkstra.awk dijkstra.txt
a-c-d-e (26)
a-c-f (11)
f-a (n/a)
</syntaxhighlight>
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
<syntaxhighlight lang="basic">100 O$ = "A" : T$ = "EF"
110 DEF FN N(P) = ASC(MID$(N$,P+(P=0),1))-64
120 DIM D(26),UNVISITED(26)
130 DIM PREVIOUS(26) : TRUE = 1
140 LET M = -1 : INFINITY = M
150 FOR I = 0 TO 26
160 LET D(I) = INFINITY : NEXT
170 FOR NE = M TO 1E38 STEP .5
180 READ C$
190 IF LEN(C$) THEN NEXT
200 DIM C(NE),FROM(NE),T(NE)
210 DIM PC(NE) : RESTORE
220 FOR I = 0 TO NE
230 READ C(I), N$
240 LET FROM(I) = FN N(1)
250 LET UNVISITED(FR(I)) = TRUE
260 LET T(I) = FN N(3)
270 LET UNVISITED(T(I)) = TRUE
290 NEXT
300 N$ = O$ : O = FN N(0)
310 D(O) = 0
320 FOR CV = O TO EMPTY STEP 0
330 FOR I = 0 TO NE
340 IF FROM(I) = CV THEN N = T(I) : D = D(CV) + C(I) : IF (D(N) = INFINITY) OR (D < D(N)) THEN D(N) = D : PREVIOUS(N) = CV : PC(N) = C(I)
350 NEXT I
360 LET UNVISITED(CV) = FALSE
370 LET MV = EMPTY
380 FOR I = 1 TO 26
390 IF UNVISITED(I) THEN MD = D(MV) * (MV <> INFINITY) + INFINITY * (MV = INFINITY) : IF (D(I) <> INFINITY) AND ((MD = INFINITY) OR (D(I) < MD)) THEN MV = I
400 NEXT I
410 LET CV = MV * (MD <> INF)
420 NEXT CV : M$ = CHR$(13)
430 PRINT "SHORTEST PATH";
440 FOR I = 1 TO LEN(T$)
450 LET N$ = MID$(T$, I, 1)
460 PRINT M$ " FROM " O$;
470 PRINT " TO "; : N = FN N(0)
480 IF D(N) = INFINITY THEN PRINT N$" DOES NOT EXIST.";
490 IF D(N) <> INFINITY THEN FOR N = N TO FALSE STEP 0 : PRINT CHR$(N + 64); : IF N < > O THEN PRINT " <- "; : N = PREVIOUS(N): NEXT N
500 IF D(N) <> INFINITY THEN PRINT : PRINT " IS "; : N = FN N(0) : PRINT D(N); : H = 15 : FOR N = N TO O STEP 0: IF N < > O THEN P = PREVIOUS(N): PRINT TAB(H)CHR$(43+18*(h=15));TAB(H+2)PC(N); :N = P: H=H+5: NEXT N
510 NEXT I
600 DATA 7,A-B
610 DATA 9,A-C
620 DATA 14,A-F
630 DATA 10,B-C
640 DATA 15,B-D
650 DATA 11,C-D
660 DATA 2,C-F
670 DATA 6,D-E
680 DATA 9,E-F
690 DATA</syntaxhighlight>
{{out}}
<pre>SHORTEST PATH
FROM A TO E <- D <- C <- A
IS 26 = 6 + 11 + 9
FROM A TO F <- C <- A
IS 11 = 2 + 9
</pre>
==={{header|Commodore BASIC}}===
This should work on any Commodore 8-bit BASIC from V2 on; with the given sample data, it even runs on an unexpanded VIC-20.
(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.)
<syntaxhighlight lang="basic">100 NV=0: REM NUMBER OF VERTICES
110 READ N$:IF N$<>"" THEN NV=NV+1:GOTO 110
120 NE=0: REM NUMBER OF EDGES
130 READ N1:IF N1 >= 0 THEN READ N2,W:NE=NE+1:GOTO 130
140 DIM VN$(NV-1),VD(NV-1,2): REM VERTEX NAMES AND DATA
150 DIM ED(NE-1,2): REM EDGE DATA
160 RESTORE
170 FOR I=0 TO NV-1
180 : READ VN$(I): REM VERTEX NAME
190 : VD(I,0) = -1: REM DISTANCE = INFINITY
200 : VD(I,1) = 0: REM NOT YET VISITED
210 : VD(I,2) = -1: REM NO PREV VERTEX YET
220 NEXT I
230 READ N$: REM SKIP SENTINEL
240 FOR I=0 TO NE-1
250 : READ ED(I,0),ED(I,1),ED(I,2): REM EDGE FROM, TO, WEIGHT
260 NEXT I
270 READ N1: REM SKIP SENTINEL
280 READ O: REM ORIGIN VERTEX
290 :
300 REM BEGIN DIJKSTRA'S
310 VD(O,0) = 0: REM DISTANCE TO ORIGIN IS 0
320 CV = 0: REM CURRENT VERTEX IS ORIGIN
330 FOR I=0 TO NE-1
340 : IF ED(I,0)<>CV THEN 390: REM SKIP EDGES NOT FROM CURRENT
350 : N=ED(I,1): REM NEIGHBOR VERTEX
360 : D=VD(CV,0) + ED(I,2): REM TOTAL DISTANCE TO NEIGHBOR THROUGH THIS PATH
370 : REM IF PATH THRU CV < DISTANCE, UPDATE DISTANCE AND PREV VERTEX
380 : IF (VD(N,0)=-1) OR (D<VD(N,0)) THEN VD(N,0) = D:VD(N,2)=CV
390 NEXT I
400 VD(CV,1)=1: REM CURRENT VERTEX HAS BEEN VISITED
410 MV=-1: REM VERTEX WITH MINIMUM DISTANCE SEEN
420 FOR I=0 TO NV-1
430 : IF VD(I,1) THEN 470: REM SKIP VISITED VERTICES
440 : REM IF THIS IS THE SMALLEST DISTANCE SEEN, REMEMBER IT
450 : MD=-1:IF MV > -1 THEN MD=VD(MV,0)
460 : IF ( VD(I,0)<>-1 ) AND ( ( MD=-1 ) OR ( VD(I,0)<MD ) ) THEN MV=I
470 NEXT I
480 IF MD=-1 THEN 510: REM END IF ALL VERTICES VISITED OR AT INFINITY
490 CV=MV
500 GOTO 330
510 PRINT "SHORTEST PATH TO EACH VERTEX FROM "VN$(O)":";CHR$(13)
520 FOR I=0 TO NV-1
530 : IF I=0 THEN 600
540 : PRINT VN$(I)":"VD(I,0)"(";
550 : IF VD(I,0)=-1 THEN 600
560 : N=I
570 : PRINT VN$(N);
580 : IF N<>O THEN PRINT "←";:N=VD(N,2):GOTO 570
590 : PRINT ")"
600 NEXT I
610 DATA A,B,C,D,E,F,""
620 DATA 0,1,7
630 DATA 0,2,9
640 DATA 0,5,14
650 DATA 1,2,10
660 DATA 1,3,15
670 DATA 2,3,11
680 DATA 2,5,2
690 DATA 3,4,6
700 DATA 4,5,9
710 DATA -1
720 DATA 0</syntaxhighlight>
{{Out}}
Paths are printed right-to-left mainly because PETSCII includes a left-facing arrow and not a right-facing one:
<pre>SHORTEST PATH TO EACH VERTEX FROM A:
B: 7 (B←A)
C: 9 (C←A)
D: 20 (D←C←A)
E: 26 (E←D←C←A)
F: 11 (F←C←A)
</pre>
==={{header|VBA}}===
<syntaxhighlight lang="vb">Class Branch
Public from As Node '[according to Dijkstra the first Node should be closest to P]
Public towards As Node
Public length As Integer '[directed length!]
Public distance As Integer '[from P to farthest node]
Public key As String
Class Node
Public key As String
Public correspondingBranch As Branch
Const INFINITY = 32767
Private Sub Dijkstra(Nodes As Collection, Branches As Collection, P As Node, Optional Q As Node)
'Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs".
'Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.
'http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf
'Problem 2. Find the path of minimum total length between two given nodes
'P and Q.
'We use the fact that, if R is a node on the minimal path from P to Q, knowledge
'of the latter implies the knowledge of the minimal path from P to A. In the
'solution presented, the minimal paths from P to the other nodes are constructed
'in order of increasing length until Q is reached.
'In the course of the solution the nodes are subdivided into three sets:
'A. the nodes for which the path of minimum length from P is known; nodes
'will be added to this set in order of increasing minimum path length from node P;
'[comments in square brackets are not by Dijkstra]
Dim a As New Collection '[of nodes (vertices)]
'B. the nodes from which the next node to be added to set A will be selected;
'this set comprises all those nodes that are connected to at least one node of
'set A but do not yet belong to A themselves;
Dim b As New Collection '[of nodes (vertices)]
'C. the remaining nodes.
Dim c As New Collection '[of nodes (vertices)]
'The Branches are also subdivided into three sets:
'I the Branches occurring in the minimal paths from node P to the nodes
'in set A;
Dim I As New Collection '[of Branches (edges)]
'II the Branches from which the next branch to be placed in set I will be
'selected; one and only one branch of this set will lead to each node in set B;
Dim II As New Collection '[of Branches (edges)]
'III. the remaining Branches (rejected or not yet considered).
Dim III As New Collection '[of Branches (edges)]
Dim u As Node, R_ As Node, dist As Integer
'To start with, all nodes are in set C and all Branches are in set III. We now
'transfer node P to set A and from then onwards repeatedly perform the following
'steps.
For Each n In Nodes
c.Add n, n.key
Next n
For Each e In Branches
III.Add e, e.key
Next e
a.Add P, P.key
c.Remove P.key
Set u = P
Do
'Step 1. Consider all Branches r connecting the node just transferred to set A
'with nodes R in sets B or C. If node R belongs to set B, we investigate whether
'the use of branch r gives rise to a shorter path from P to R than the known
'path that uses the corresponding branch in set II. If this is not so, branch r is
'rejected; if, however, use of branch r results in a shorter connexion between P
'and R than hitherto obtained, it replaces the corresponding branch in set II
'and the latter is rejected. If the node R belongs to set C, it is added to set B and
'branch r is added to set II.
For Each r In III
If r.from Is u Then
Set R_ = r.towards
If Belongs(R_, c) Then
c.Remove R_.key
b.Add R_, R_.key
Set R_.correspondingBranch = r
If u.correspondingBranch Is Nothing Then
R_.correspondingBranch.distance = r.length
Else
R_.correspondingBranch.distance = u.correspondingBranch.distance + r.length
End If
III.Remove r.key '[not mentioned by Dijkstra ...]
II.Add r, r.key
Else
If Belongs(R_, b) Then '[initially B is empty ...]
If R_.correspondingBranch.distance > u.correspondingBranch.distance + r.length Then
II.Remove R_.correspondingBranch.key
II.Add r, r.key
Set R_.correspondingBranch = r '[needed in step 2.]
R_.correspondingBranch.distance = u.correspondingBranch.distance + r.length
End If
End If
End If
End If
Next r
'Step 2. Every node in set B can be connected to node P in only one way
'if we restrict ourselves to Branches from set I and one from set II. In this sense
'each node in set B has a distance from node P: the node with minimum distance
'from P is transferred from set B to set A, and the corresponding branch is transferred
'from set II to set I. We then return to step I and repeat the process
'until node Q is transferred to set A. Then the solution has been found.
dist = INFINITY
Set u = Nothing
For Each n In b
If dist > n.correspondingBranch.distance Then
dist = n.correspondingBranch.distance
Set u = n
End If
Next n
b.Remove u.key
a.Add u, u.key
II.Remove u.correspondingBranch.key
I.Add u.correspondingBranch, u.correspondingBranch.key
Loop Until IIf(Q Is Nothing, a.Count = Nodes.Count, u Is Q)
If Not Q Is Nothing Then GetPath Q
End Sub
Private Function Belongs(n As Node, col As Collection) As Boolean
Dim obj As Node
On Error GoTo err
Belongs = True
Set obj = col(n.key)
Exit Function
err:
Belongs = False
End Function
Private Sub GetPath(Target As Node)
Dim path As String
If Target.correspondingBranch Is Nothing Then
path = "no path"
Else
path = Target.key
Set u = Target
Do While Not u.correspondingBranch Is Nothing
path = u.correspondingBranch.from.key & " " & path
Set u = u.correspondingBranch.from
Loop
Debug.Print u.key, Target.key, Target.correspondingBranch.distance, path
End If
End Sub
Public Sub test()
Dim a As New Node, b As New Node, c As New Node, d As New Node, e As New Node, f As New Node
Dim ab As New Branch, ac As New Branch, af As New Branch, bc As New Branch, bd As New Branch
Dim cd As New Branch, cf As New Branch, de As New Branch, ef As New Branch
Set ab.from = a: Set ab.towards = b: ab.length = 7: ab.key = "ab": ab.distance = INFINITY
Set ac.from = a: Set ac.towards = c: ac.length = 9: ac.key = "ac": ac.distance = INFINITY
Set af.from = a: Set af.towards = f: af.length = 14: af.key = "af": af.distance = INFINITY
Set bc.from = b: Set bc.towards = c: bc.length = 10: bc.key = "bc": bc.distance = INFINITY
Set bd.from = b: Set bd.towards = d: bd.length = 15: bd.key = "bd": bd.distance = INFINITY
Set cd.from = c: Set cd.towards = d: cd.length = 11: cd.key = "cd": cd.distance = INFINITY
Set cf.from = c: Set cf.towards = f: cf.length = 2: cf.key = "cf": cf.distance = INFINITY
Set de.from = d: Set de.towards = e: de.length = 6: de.key = "de": de.distance = INFINITY
Set ef.from = e: Set ef.towards = f: ef.length = 9: ef.key = "ef": ef.distance = INFINITY
a.key = "a"
b.key = "b"
c.key = "c"
d.key = "d"
e.key = "e"
f.key = "f"
Dim testNodes As New Collection
Dim testBranches As New Collection
testNodes.Add a, "a"
testNodes.Add b, "b"
testNodes.Add c, "c"
testNodes.Add d, "d"
testNodes.Add e, "e"
testNodes.Add f, "f"
testBranches.Add ab, "ab"
testBranches.Add ac, "ac"
testBranches.Add af, "af"
testBranches.Add bc, "bc"
testBranches.Add bd, "bd"
testBranches.Add cd, "cd"
testBranches.Add cf, "cf"
testBranches.Add de, "de"
testBranches.Add ef, "ef"
Debug.Print "From", "To", "Distance", "Path"
'[Call Dijkstra with target:]
Dijkstra testNodes, testBranches, a, e
'[Call Dijkstra without target computes paths to all reachable nodes:]
Dijkstra testNodes, testBranches, a
GetPath f
End Sub</syntaxhighlight>{{out}}<pre>From To Distance Path
a e 26 a c d e
a f 11 a c f</pre>
=={{header|C}}==
Line 2,335 ⟶ 3,015:
;; | f | 11 | (a c f) |
</syntaxhighlight>
=={{header|Common Lisp}}==
Line 2,702 ⟶ 3,302:
5: distance = 11, 0 --> 2 --> 5
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
global con[][] n .
proc read . .
repeat
s$ = input
until s$ = ""
a = (strcode substr s$ 1 1) - 96
b = (strcode substr s$ 3 1) - 96
d = number substr s$ 5 9
if a > len con[][]
len con[][] a
.
con[a][] &= b
con[a][] &= d
.
con[][] &= [ ]
n = len con[][]
.
read
#
len cost[] n
len prev[] n
#
proc dijkstra . .
for i = 2 to len cost[]
cost[i] = 1 / 0
.
len todo[] n
todo[1] = 1
repeat
min = 1 / 0
a = 0
for i to len todo[]
if todo[i] = 1 and cost[i] < min
min = cost[i]
a = i
.
.
until a = 0
todo[a] = 0
for i = 1 step 2 to len con[a][] - 1
b = con[a][i]
c = con[a][i + 1]
if cost[a] + c < cost[b]
cost[b] = cost[a] + c
prev[b] = a
todo[b] = 1
.
.
.
.
dijkstra
#
func$ gpath nd$ .
nd = strcode nd$ - 96
while nd <> 1
s$ = " -> " & strchar (nd + 96) & s$
nd = prev[nd]
.
return "a" & s$
.
print gpath "e"
print gpath "f"
#
input_data
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
</syntaxhighlight>
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">
(defvar path-list '((a b 7)
(a c 9)
(a
(
(
(defun calculate-shortest-path (path-list)
(let (shortest-path)
(dolist (path path-list)
(add-to-list 'shortest-path (list (nth 0 path)
(nth 1 path)
nil
(nth 2 path))
't))
(dolist (path path-list)
(dolist (short-path shortest-path)
(when (equal (nth 0 path) (nth 1 short-path))
(let ((test-path (list (nth 0 short-path)
(nth 1 path)
(nth 0 path)
(+ (nth 2 path) (nth 3 short-path))))
is-path-found)
(dolist (short-path1 shortest-path)
(when (equal (seq-take test-path 2)
(seq-take short-path1 2))
(setq is-path-found 't)
(when (> (nth 3 short-path1) (nth 3 test-path))
(setcdr (cdr short-path1) (cddr test-path)))))
(when (not is-path-found)
(add-to-list 'shortest-path test-path 't))))))
shortest-path))
(add-to-list 'point-list to)
(setq matched-path
(seq-find (lambda (path) (equal (list from to) (seq-take path 2)))
shortest-path-list))
(add-to-list 'point-list (nth 2 matched-path))
(setq to (nth 2 matched-path))
(setq matched-path
(seq-find (lambda (path) (equal (list from to) (seq-take path 2)))
shortest-path-list)))
(if matched-path
(progn
(list 'route point-list 'distance distance))
nil)))
(format "%S" (find-shortest-route 'a 'e path-list))
</syntaxhighlight>
Line 2,804 ⟶ 3,451:
<pre>
(route (a c d e) distance 26)
</pre>
Line 2,919 ⟶ 3,559:
Some [A; C; D; E]
Some [A; C; F]
</pre>
=={{header|Forth}}==
{{trans|Commodore BASIC}}
<syntaxhighlight lang="FORTH">\ utility routine to increment a variable
: 1+! 1 swap +! ;
\ edge data
variable edge-count
0 edge-count !
create edges
'a , 'b , 7 , edge-count 1+!
'a , 'c , 9 , edge-count 1+!
'a , 'f , 14 , edge-count 1+!
'b , 'c , 10 , edge-count 1+!
'b , 'd , 15 , edge-count 1+!
'c , 'd , 11 , edge-count 1+!
'c , 'f , 2 , edge-count 1+!
'd , 'e , 6 , edge-count 1+!
'e , 'f , 9 , edge-count 1+!
\ with accessors
: edge 3 * cells edges + ;
: edge-from edge ;
: edge-to edge 1 cells + ;
: edge-weight edge 2 cells + ;
\ vertex data and acccessor
create vertex-names edge-count @ 2 * cells allot
: vertex-name cells vertex-names + ;
variable vertex-count
0 vertex-count !
\ routine to look up a vertex by name
: find-vertex
-1 swap
vertex-count @ 0 ?do
dup i vertex-name @ = if swap drop i swap leave then
loop
drop
;
\ routine to add a new vertex name if not found
: add-vertex
dup find-vertex dup -1 = if
swap vertex-count @ vertex-name !
vertex-count dup @ swap 1+!
swap drop
else
swap
drop
then
;
\ routine to add vertices to name table and replace names with indices in edges
: get-vertices
edge-count @ 0 ?do
i edge-from @ add-vertex i edge-from !
i edge-to @ add-vertex i edge-to !
loop
;
\ call it
get-vertices
\ variables to hold state during algorithm run
create been-visited
vertex-count @ cells allot
: visited cells been-visited + ;
create prior-vertices
vertex-count @ cells allot
: prior-vertex cells prior-vertices + ;
create distances
vertex-count @ cells allot
: distance cells distances + ;
variable origin
variable current-vertex
variable neighbor
variable current-distance
variable tentative
variable closest-vertex
variable minimum-distance
variable vertex
\ call with origin vertex name on stack
: dijkstra ( origin -- )
find-vertex origin !
been-visited vertex-count @ cells 0 fill
prior-vertices vertex-count @ cells -1 fill
distances vertex-count @ cells -1 fill
0 origin @ distance ! \ distance to origin is 0
origin @ current-vertex ! \ current vertex is the origin
begin
edge-count @ 0 ?do
i edge-from @ current-vertex @ = if \ if edge is from current
i edge-to @ neighbor ! \ neighbor vertex
neighbor @ distance @ current-distance !
current-vertex @ distance @ i edge-weight @ + tentative !
current-distance @ -1 = tentative @ current-distance @ < or if
tentative @ neighbor @ distance !
current-vertex @ neighbor @ prior-vertex !
then
else
then
loop
1 current-vertex @ visited ! \ current vertex has now been visited
-1 closest-vertex !
vertex-count @ 0 ?do
i visited @ 0= if
-1 minimum-distance !
closest-vertex @ dup -1 <> if
distance @ minimum-distance !
else
drop
then
i distance @ -1 <>
minimum-distance @ -1 = i distance @ minimum-distance @ < or
and if
i closest-vertex !
then
then
loop
closest-vertex @ current-vertex !
current-vertex @ -1 = until
cr
." Shortest path to each vertex from " origin @ vertex-name @ emit ': emit cr
vertex-count @ 0 ?do
i origin @ <> if
i vertex-name @ emit ." : " i distance @ dup
-1 = if
drop
." ∞ (unreachable)"
else
.
'( emit
i vertex !
begin
vertex @ vertex-name @ emit
vertex @ origin @ <> while
." ←"
vertex @ prior-vertex @ vertex !
repeat
') emit
then
cr
then
loop
;</syntaxhighlight>
{{Out}}
<pre>'a dijkstra
Shortest path to each vertex from a:
b: 7 (b←a)
c: 9 (c←a)
f: 11 (f←c←a)
d: 20 (d←c←a)
e: 26 (e←d←c←a)
ok
'b dijkstra
Shortest path to each vertex from b:
a: ∞ (unreachable)
c: 10 (c←b)
f: 12 (f←c←b)
d: 15 (d←b)
e: 21 (e←d←b)
ok</pre>
=={{header|Fortran}}==
<syntaxhighlight lang="FORTRAN">
program main
! Demo of Dijkstra's algorithm.
! Translation of Rosetta code Pascal version
implicit none
!
! PARAMETER definitions
!
integer , parameter :: nr_nodes = 6 , start_index = 0
!
! Derived Type definitions
!
enum , bind(c)
enumerator :: SetA , SetB , SetC
end enum
!
type tnode
integer :: nodeset
integer :: previndex ! previous node in path leading to this node
integer :: pathlength ! total length of path to this node
end type tnode
!
! Local variable declarations
!
integer :: branchlength , j , j_min , k , lasttoseta , minlength , nrinseta , triallength
character(5) :: holder
integer , dimension(0:nr_nodes - 1 , 0:nr_nodes - 1) :: lengths
character(132) :: lineout
type (tnode) , dimension(0:nr_nodes - 1) :: nodes
! character(2) , dimension(0:nr_nodes - 1) :: node_names
character(15),dimension(0:nr_nodes-1) :: node_names
! Correct values
!Shortest paths from node a:
! b: length 7, a -> b
! c: length 9, a -> c
! d: length 20, a -> c -> d
! e: length 26, a -> c -> d -> e
! f: length 11, a -> c -> f
!
nodes%nodeset = 0
nodes%previndex = 0
nodes%pathlength = 0
node_names = (/'a' , 'b' , 'c' , 'd' , 'e' , 'f'/)
!
! lengths[j,k] = length of branch j -> k, or -1 if no such branch exists.
lengths(0 , :) = (/ - 1 , 7 , 9 , -1 , -1 , 14/)
lengths(1 , :) = (/ - 1 , -1 , 10 , 15 , -1 , -1/)
lengths(2 , :) = (/ - 1 , -1 , -1 , 11 , -1 , 2/)
lengths(3 , :) = (/ - 1 , -1 , -1 , -1 , 6 , -1/)
lengths(4 , :) = (/ - 1 , -1 , -1 , -1 , -1 , 9/)
lengths(5 , :) = (/ - 1 , -1 , -1 , -1 , -1 , -1/)
do j = 0 , nr_nodes - 1
nodes(j)%nodeset = SetC
enddo
! Begin by transferring the start node to set A
nodes(start_index)%nodeset = SetA
nodes(start_index)%pathlength = 0
nrinseta = 1
lasttoseta = start_index
! Transfer nodes to set A one at a time, until all have been transferred
do while (nrinseta<nr_nodes)
! Step 1: Work through branches leading from the node that was most recently
! transferred to set A, and deal with end nodes in set B or set C.
do j = 0 , nr_nodes - 1
branchlength = lengths(lasttoseta , j)
if (branchlength>=0) then
! If the end node is in set B, and the path to the end node via lastToSetA
! is shorter than the existing path, then update the path.
if (nodes(j)%nodeset==SetB) then
triallength = nodes(lasttoseta)%pathlength + branchlength
if (triallength<nodes(j)%pathlength) then
nodes(j)%previndex = lasttoseta
nodes(j)%pathlength = triallength
endif
! If the end node is in set C, transfer it to set B.
elseif (nodes(j)%nodeset==SetC) then
nodes(j)%nodeset = SetB
nodes(j)%previndex = lasttoseta
nodes(j)%pathlength = nodes(lasttoseta)%pathlength + branchlength
endif
endif
enddo
! Step 2: Find the node in set B with the smallest path length,
! and transfer that node to set A.
! (Note that set B cannot be empty at this point.)
minlength = -1
j_min = -1
do j = 0 , nr_nodes - 1
if (nodes(j)%nodeset==SetB) then
if ((j_min== - 1).or.(nodes(j)%pathlength<minlength)) then
j_min = j
minlength = nodes(j)%pathlength
endif
endif
enddo
nodes(j_min)%nodeset = SetA
nrinseta = nrinseta + 1
lasttoseta = j_min
enddo
print* , 'Shortest paths from node ',trim(node_names(start_index))
do j = 0 , nr_nodes - 1
if (j/=start_index) then
k = j
lineout = node_names(k)
pete_loop: do
k = nodes(k)%previndex
lineout = trim(node_names(k)) // ' -> ' // trim(lineout)
if (k==start_index) exit pete_loop
enddo pete_loop
write (holder , '(i0)') nodes(j)%pathlength
lineout = trim(adjustl(node_names(j))) // ': length ' // trim(adjustl(holder)) // ', ' // trim(lineout)
print * , lineout
endif
enddo
stop
end program main
</syntaxhighlight>
{{out}}
<pre>
Shortest paths from node a
b: length 7, a -> b
c: length 9, a -> c
d: length 20, a -> c -> d
e: length 26, a -> c -> d -> e
f: length 11, a -> c -> f
</pre>
=={{header|Free Pascal}}==
Requires FPC version of at least 3.2.0.
For convenience, let's try to use priority queue from[[https://rosettacode.org/wiki/Priority_queue#Advanced_version]].
<syntaxhighlight lang="pascal">
program SsspDemo;
{$mode delphi}
uses
SysUtils, Generics.Collections, PQueue;
type
TArc = record
Target: string;
Cost: Integer;
constructor Make(const t: string; c: Integer);
end;
TDigraph = class
strict private
FGraph: TObjectDictionary<string, TList<TArc>>;
public
const
INF_WEIGHT = MaxInt;
constructor Create;
destructor Destroy; override;
procedure AddNode(const n: string);
procedure AddArc(const s, t: string; c: Integer);
function AdjacencyList(const n: string): TList<TArc>;
function DijkstraSssp(const From: string; out PathTree: TDictionary<string, string>;
out Dist: TDictionary<string, Integer>): Boolean;
end;
constructor TArc.Make(const t: string; c: Integer);
begin
Target := t;
Cost := c;
end;
function CostCmp(const L, R: TArc): Boolean;
begin
Result := L.Cost > R.Cost;
end;
constructor TDigraph.Create;
begin
FGraph := TObjectDictionary<string, TList<TArc>>.Create([doOwnsValues]);
end;
destructor TDigraph.Destroy;
begin
FGraph.Free;
inherited;
end;
procedure TDigraph.AddNode(const n: string);
begin
if not FGraph.ContainsKey(n) then
FGraph.Add(n, TList<TArc>.Create);
end;
procedure TDigraph.AddArc(const s, t: string; c: Integer);
begin
AddNode(s);
AddNode(t);
if s <> t then
FGraph.Items[s].Add(TArc.Make(t, c));
end;
function TDigraph.AdjacencyList(const n: string): TList<TArc>;
begin
if not FGraph.TryGetValue(n, Result) then
Result := nil;
end;
function TDigraph.DijkstraSssp(const From: string; out PathTree: TDictionary<string, string>;
out Dist: TDictionary<string, Integer>): Boolean;
var
q: TPriorityQueue<TArc>;
Reached: THashSet<string>;
Handles: TDictionary<string, q.THandle>;
Next, Arc, Relax: TArc;
h: q.THandle = -1;
k: string;
begin
if not FGraph.ContainsKey(From) then exit(False);
Reached := THashSet<string>.Create;
Handles := TDictionary<string, q.THandle>.Create;
Dist := TDictionary<string, Integer>.Create;
for k in FGraph.Keys do
Dist.Add(k, INF_WEIGHT);
PathTree := TDictionary<string, string>.Create;
q := TPriorityQueue<TArc>.Create(@CostCmp);
PathTree.Add(From, '');
Next := TArc.Make(From, 0);
repeat
Reached.Add(Next.Target);
Dist[Next.Target] := Next.Cost;
for Arc in AdjacencyList(Next.Target) do
if not Reached.Contains(Arc.Target)then
if Handles.TryGetValue(Arc.Target, h) then begin
Relax := q.GetValue(h);
if Arc.Cost + Next.Cost < Relax.Cost then begin
q.Update(h, TArc.Make(Relax.Target, Arc.Cost + Next.Cost));
PathTree[Arc.Target] := Next.Target;
end
end else begin
Handles.Add(Arc.Target, q.Push(TArc.Make(Arc.Target, Arc.Cost + Next.Cost)));
PathTree.Add(Arc.Target, Next.Target);
end;
until not q.TryPop(Next);
Reached.Free;
Handles.Free;
q.Free;
Result := True;
end;
function ExtractPath(PathTree: TDictionary<string, string>; n: string): TStringArray;
begin
if not PathTree.ContainsKey(n) then exit(nil);
with TList<string>.Create do begin
repeat
Add(n);
n := PathTree[n];
until n = '';
Reverse;
Result := ToArray;
Free;
end;
end;
const
PathFmt = 'shortest path from "%s" to "%s": %s (cost = %d)';
var
g: TDigraph;
Path: TDictionary<string, string>;
Dist: TDictionary<string, Integer>;
begin
g := TDigraph.Create;
g.AddArc('a', 'b', 7); g.AddArc('a', 'c', 9); g.AddArc('a', 'f', 14);
g.AddArc('b', 'c', 10); g.AddArc('b', 'd', 15); g.AddArc('c', 'd', 11);
g.AddArc('c', 'f', 2); g.AddArc('d', 'e', 6); g.AddArc('e', 'f', 9);
g.DijkstraSssp('a', Path, Dist);
WriteLn(Format(PathFmt, ['a', 'e', string.Join('->', ExtractPath(Path, 'e')), Dist['e']]));
WriteLn(Format(PathFmt, ['a', 'f', string.Join('->', ExtractPath(Path, 'f')), Dist['f']]));
g.Free;
Path.Free;
Dist.Free;
readln;
end.
</syntaxhighlight>
{{out}}
<pre>
shortest path from "a" to "e": a->c->d->e (cost = 26)
shortest path from "a" to "f": a->c->f (cost = 11)
</pre>
Line 3,455 ⟶ 4,564:
NB. verbs and adverb
parse_table=: ;:@:(LF&= [;._2 -.&CR)
mp=:
min=: <./ NB. minimum
Index=: (i.`)(`:6) NB. Index adverb
Line 3,957 ⟶ 5,066:
=={{header|Julia}}==
{{works with|Julia|
<syntaxhighlight lang="julia">
struct Digraph{T <: Real,U}
edges::Dict{Tuple{U,U},T}
verts::Set{U}
Line 4,008 ⟶ 5,119:
else
while dest != source
dest = prev[dest]
end
return rst, cost
end
Line 4,017 ⟶ 5,128:
# testgraph = [("a", "b", 1), ("b", "e", 2), ("a", "e", 4)]
const testgraph = [("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)]
function testpaths()
g = Digraph(testgraph)
src, dst = "a", "e"
path, cost = dijkstrapath(g, src, dst)
"no possible path" : join(path, " → "), " (cost $cost)")
# Print all possible paths
@printf("\n%4s | %3s | %s\n", "src", "dst", "path")
@printf("----------------\n")
for src in vertices(g), dst in vertices(g)
path, cost = dijkstrapath(g, src, dst)
@printf("%4s | %3s | %s\n", src, dst, isempty(path) ? "no possible path" : join(path, " → ") * " ($cost)")
end
end
testpaths()</syntaxhighlight>{{out}}
<pre>Shortest path from a to e: a → c → d → e (cost 26)
Line 6,400 ⟶ 7,514:
def edges: {|
{ from: vertex´'a', to: vertex´'b', cost: 7"1" },
{ from: vertex´'a', to: vertex´'c', cost: 9"1" },
{ from: vertex´'a', to: vertex´'f', cost: 14"1" },
{ from: vertex´'b', to: vertex´'c', cost: 10"1" },
{ from: vertex´'b', to: vertex´'d', cost: 15"1" },
{ from: vertex´'c', to: vertex´'d', cost: 11"1" },
{ from: vertex´'c', to: vertex´'f', cost: 2"1" },
{ from: vertex´'d', to: vertex´'e', cost: 6"1" },
{ from: vertex´'e', to: vertex´'f', cost: 9"1" }
|};
def fromA: vertex´'a' -> shortestPaths&{graph: $edges};
($fromA matching {|{to:vertex´'e'}|})... -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);
' -> !OUT::write
($fromA matching {|{to:vertex´'f'}|})... -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);
' -> !OUT::write
</syntaxhighlight>
Line 6,494 ⟶ 7,608:
route from a to e is: a -> c -> f -> e
</pre>
=={{header|Wren}}==
Line 6,680 ⟶ 7,615:
{{libheader|Wren-sort}}
{{libheader|Wren-set}}
<syntaxhighlight lang="
import "./trait" for Comparable
import "./sort" for Cmp, Sort
import "./set" for Set
var Edge = Tuple.create("Edge", ["v1", "v2", "dist"])
| |||