Dijkstra's algorithm: Difference between revisions
m
→{{header|EasyLang}}
| (41 intermediate revisions by 15 users not shown) | |||
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
</pre>
=={{header|Arturo}}==
{{trans|Nim}}
<syntaxhighlight lang="arturo">define :graph [vertices, neighbours][]
initGraph: function [edges][
Line 745 ⟶ 683:
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 751 ⟶ 689:
<pre>Shortest path from 'a' to 'e': a -> c -> d -> e
Shortest path from 'a' to 'f': a -> c -> f</pre>
=={{header|ATS}}==
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">
(*------------------------------------------------------------------*)
(* Dijkstra's algorithm. *)
(* I demonstrate Dijkstra's algorithm using a rudimentary priority
queue. For a practical implementation, you would use a fast
implementation of priority queue. *)
%{^
#include <math.h>
%}
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
#define NIL list_nil ()
#define :: list_cons
typedef flt = double
macdef zero = 0.0
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
{i, j, n : int | 0 <= i; i < j; 1 <= n}
()
:<prf> [i * n < j * n] void =
mul_compare_lte {i + 1, j, n} ()
(*------------------------------------------------------------------*)
(* Constructing a graph. *)
fn
extract_vertices
(edges : List @(string, string, double))
:<!wrt> [n : nat]
@(arrayref (string, n),
size_t n) =
let
fun
list_the_vertices
{m : nat}
{n0 : nat}
.<m>.
(edges : list (@(string, string, double), m),
accum : list (string, n0),
n0 : size_t n0)
:<!wrt> [n1 : nat]
@(list (string, n1), size_t n1) =
case+ edges of
| NIL => @(accum, n0)
| @(v1, v2, _) :: tail =>
let
implement list_find$pred<string> x = (x = v1)
in
case+ list_find_opt accum of
| ~ None_vt () =>
let
implement list_find$pred<string> x = (x = v2)
in
case+ list_find_opt accum of
| ~ None_vt () =>
list_the_vertices (tail, v2 :: v1 :: accum,
succ (succ n0))
| ~ Some_vt _ =>
list_the_vertices (tail, v1 :: accum, succ n0)
end
| ~ Some_vt _ =>
let
implement list_find$pred<string> x = (x = v2)
in
case+ list_find_opt accum of
| ~ None_vt () =>
list_the_vertices (tail, v2 :: accum, succ n0)
| ~ Some_vt _ => list_the_vertices (tail, accum, n0)
end
end
prval () = lemma_list_param edges
val @(vertex_lst, n) = list_the_vertices (edges, NIL, i2sz 0)
val vertex_arr = arrayref_make_list<string> (sz2i n, vertex_lst)
in
@(vertex_arr, n)
end
fn
vertex_name_to_index
{n : int}
(vertex_arr : arrayref (string, n),
n : size_t n,
name : string)
:<!ref> Option ([i : nat | i < n] size_t i) =
let
fun
loop {i : nat | i <= n}
.<n - i>.
(i : size_t i)
:<!ref> Option ([i : nat | i < n] size_t i) =
if i = n then
None ()
else if name = vertex_arr[i] then
Some i
else
loop (succ i)
prval () = lemma_arrayref_param vertex_arr
in
loop (i2sz 0)
end
fn
make_adjacency_matrix
(edges : List @(string, string, double))
:<!refwrt> [n : nat]
@(matrixref (flt, n, n),
arrayref (string, n),
size_t n) =
let
val @(vertex_arr, n) = extract_vertices edges
val adj_matrix = matrixref_make_elt<flt> (n, n, infinity)
fun
loop {m : nat}
.<m>.
(edges : list (@(string, string, double), m))
:<!refwrt> void =
case+ edges of
| NIL => ()
| @(v1, v2, cost) :: tail =>
let
val- Some i = vertex_name_to_index (vertex_arr, n, v1)
and Some j = vertex_name_to_index (vertex_arr, n, v2)
in
adj_matrix[i, n, j] := cost;
loop tail
end
prval () = lemma_list_param edges
in
loop edges;
@(adj_matrix, vertex_arr, n)
end
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
fun
loop {m : nat}
.<m>.
(path : list ([i : nat | i < n] size_t i, m),
column_no : size_t)
: size_t =
case+ path of
| NIL => column_no
| 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
case+ cost_opt of
| 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
(*------------------------------------------------------------------*)
(* Dijkstra's algorithm. *)
fn
dijkstra_algorithm
{n : int}
{source : nat | source < n}
(adj_matrix : matrixref (flt, n, n),
n : size_t n,
source : size_t source)
(* Returns total-costs and previous-hops arrays. *)
:<!refwrt> @(arrayref (flt, n),
arrayref ([i : nat | i <= n] size_t i, n)) =
let
prval () = lemma_matrixref_param adj_matrix
typedef index_t = [i : nat | i <= n] size_t i
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; m <= m_max]
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 >> pqueue_t n,
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
{m0 : pos | m0 + n <= m_max}
.<m0>.
(pq : &pqueue_t m0 >> pqueue_t m1)
:<!refwrt> #[m1 : nat | m1 < m0]
@(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 () = mul_elim pf_qlimit0
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
fun
loop_over_vertices
{v : nat | v <= n}
{m0 : nat | qsize <= m0; m0 <= qsize + v}
.<n - v>.
(pq : &pqueue_t m0 >> pqueue_t m1,
v : size_t v)
:<!refwrt> #[m1 : int | qsize <= m1; m1 <= qsize + n]
void =
if v = n then
()
else if ~active[v] then
loop_over_vertices {v + 1} {m0} (pq, succ v)
else
let
val alternative = cost[u] + adj_matrix[u, n, v]
in
if alternative < cost[v] then
let
prval () = prop_verify {m0 < m_max} ()
in
cost[v] := alternative;
prev[v] := u;
(* Rather than lower the priority of v, this
implementation inserts a new entry for v and
ignores obsolete queue entries. Queue entries
are obsolete if the vertex's entry in the
"active" array is false. *)
pqueue_insert<flt><defined_index_t>
{m_max} {m0}
(pq, @(alternative, v));
loop_over_vertices {v + 1} {m0 + 1}
(pq, succ v)
end
else
loop_over_vertices {v + 1} {m0} (pq, succ v)
end
val () = loop_over_vertices {0} {qsize} (pq, i2sz 0)
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
fn
least_cost_path
{n : int}
(source : [i : nat | i < n] size_t i,
prev : arrayref ([i : nat | i <= n] size_t i, n),
n : size_t n,
destination : [i : nat | i < n] size_t i)
:<!refwrt> Option (List1 ([i : nat | i < n] size_t i)) =
let
prval () = lemma_arrayref_param prev
typedef index_t = [i : nat | i <= n] size_t i
typedef defined_index_t = [i : nat | i < n] size_t i
val index_t_undefined : size_t n = n
fun
loop {i : nat | i <= n}
.<n - i>.
(u : defined_index_t,
accum : List1 defined_index_t,
loop_counter : size_t i)
:<!refwrt> Option (List1 defined_index_t) =
if loop_counter = n then
None ()
else if u = source then
Some accum
else
let
val previous = prev[u]
in
if previous = index_t_undefined then
None ()
else
loop (previous, previous :: accum, succ loop_counter)
end
in
loop (destination, destination :: NIL, i2sz 0)
end
(*------------------------------------------------------------------*)
val example_edges =
$list (@("a", "b", 7.0),
@("a", "c", 9.0),
@("a", "f", 14.0),
@("b", "c", 10.0),
@("b", "d", 15.0),
@("c", "d", 11.0),
@("c", "f", 2.0),
@("d", "e", 6.0),
@("e", "f", 9.0))
implement
main0 () =
let
val @(adj_matrix, vertex_arr, n) =
make_adjacency_matrix example_edges
prval [n : int] EQINT () = eqint_make_guint n
val- Some a = vertex_name_to_index (vertex_arr, n, "a")
val- Some e = vertex_name_to_index (vertex_arr, n, "e")
val- Some f = vertex_name_to_index (vertex_arr, n, "f")
val @(cost, prev) = dijkstra_algorithm (adj_matrix, n, a)
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
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW dijkstra-algorithm.dats -lgc && ./a.out
The requested paths:
a -> c -> d -> e (cost = 26.000000)
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}}==
<
nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
for each, line in StrSplit(data, "`n" , "`r")
Line 797 ⟶ 1,541:
count := A_Index
return count
}</
Examples:<
(
A B 7
Line 856 ⟶ 1,600:
GuiClose:
ExitApp
return</
Outputs:<pre>A > C 9
C > F 2
Line 862 ⟶ 1,606:
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}}==
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 ⟶ 2,188:
return 0;
}
</syntaxhighlight>
output
26 acde
=={{header|C sharp|C#}}==
{{works with|C sharp|7}}
<
using static System.String;
using static System.Console;
Line 1,187 ⟶ 2,331:
}
}</
{{out}}
<pre>
Line 1,210 ⟶ 2,354:
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,330 ⟶ 2,474:
return 0;
}</
----
Line 1,344 ⟶ 2,488:
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,471 ⟶ 2,615:
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.
Save this file as DijkstraRosetta.cafe.
To run the file type
CafeOBJ> in DijkstraRosetta.cafe
at the CafeOBJ command prompt.
CafeOBJ is primarily a first order specification language which can also be used as a functional programming language.
Being first order, we make no use higher order functions such as map.
There is a minimal library of basic types such as natural numbers, integers, floating point number, and character string.
There are no libraries for arrays, lists, trees, graphs.
Hence the user written list module.
Input
A directed positively weighted graph. The graph is represented as a list of 4tuples containing directed edges of the form (start, end, edgeDist,pathDist)
The tuple (start, start,0,0) means there is zero distance from start to start.
Ouput
1) a list of 4-tuples with each tuple represents a node N, its source node, length of the connecting edge to N, and the shortest distance from the some starting node to N .
2) a list of nodes on the shortest path from a chosen start to some chosen end node.
Note needs a bit more work to exactly match the specified Rosetta Dijkstra task.
"
-- some system settings
-- Most important is memoization (memo) which stores the value of a function instead of recomputing it each time the function is called.
full reset
set step off
set print mode :fancy
set stats off
set verbose off
set quiet on
set memo on
-- A module defining a simple parameterized list.
mod! LIST(T :: TRIV) principal-sort List {
[Elt < List ]
op nil : -> List
op (_:_) : List List -> List {memo assoc id: nil}
op reverse_ : List -> List
op head_ : List -> Elt
var e : Elt
var l : List
eq reverse nil = nil .
eq reverse (e : l) = (reverse l) : e .
eq head e : l = e .
}
-- Main module
mod! DIJKSTRA {
-- We use two different list notations, one for edges the other for paths.
-- EdgeList : A four tuple used to store graph and paths and shortest distance
-- start, end, edgeDist,pathDist
pr(LIST(4TUPLE(CHARACTER,CHARACTER,INT,INT)) *{sort List -> EdgeList, op (_:_) -> (_:e_), op nil -> nilE})
-- PathList : A list of characters used to store final shortest path.
pr(LIST(CHARACTER) *{sort List -> PathList, op (_:_) -> (_:p_), op nil -> nilP})
op dijkstra___ : Character EdgeList EdgeList -> EdgeList
op exploreNeighbours___ : Character EdgeList EdgeList -> 4Tuple {memo}
ops inf finishedI : -> Int
op finishedC : -> Character
op currDist__ : Character EdgeList -> Int
op relax__ : EdgeList EdgeList -> EdgeList
op connectedTo__ : Character EdgeList -> Bool
op nextNode2Explore_ : EdgeList -> 4Tuple
op connectedList___ : EdgeList Character EdgeList -> EdgeList
op unvisitedList__ : EdgeList EdgeList -> EdgeList
op SP___ : Character Character EdgeList -> PathList
vars eD pD eD1 pD1 eD2 pD2 source : Int
vars graph permanent xs : EdgeList
vars t t1 t2 : 4Tuple
vars s f z startVertex currentVertex : Character
eq inf = 500 .
eq finishedI = -1 .
eq finishedC = 'X' .
-- Main dijkstra function
eq dijkstra startVertex graph permanent =
if
(exploreNeighbours startVertex permanent graph) == << finishedC ; finishedC ; finishedI ; finishedI >>
then permanent
else
(dijkstra startVertex graph ( ((exploreNeighbours startVertex permanent graph) :e permanent))) fi .
eq exploreNeighbours startVertex permanent graph =
(nextNode2Explore (relax (unvisitedList (connectedList graph startVertex permanent) permanent) permanent )) .
-- nextNode2Explore takes a list of records and returns a record with the minimum 4th element else finished
eq nextNode2Explore nilE = << finishedC ; finishedC ; finishedI ; finishedI >> .
eq nextNode2Explore (t1 :e nilE) = t1 .
eq nextNode2Explore (t2 :e (t1 :e xs)) = if (4* t1) < (4* t2) then t1
else
nextNode2Explore (t2 :e xs) fi .
-- relaxes all edges leaving y
eq relax nilE permanent = nilE .
eq relax (<< s ; f ; eD ; pD >> :e xs) permanent =
if
(currDist s permanent) < pD
then
<< f ; s ; eD ; ((currDist s permanent) + eD) >> :e (relax xs permanent)
else
<< f ; s ; eD ; pD >> :e (relax xs permanent) fi .
-- Get the current best distance for a particular vertex s.
eq currDist s nilE = inf .
eq currDist s (t :e permanent) = if ((1* t) == s) then (4* t ) else
(currDist s permanent) fi .
eq connectedTo z nilE = false .
eq connectedTo z ((<< s ; f ; eD ; pD >>) :e xs) = if (s == z) then true else (connectedTo z xs) fi .
eq connectedList nilE s permanent = nilE .
eq connectedList (t :e graph) s permanent = if (connectedTo s permanent) then
(t :e (connectedList graph s permanent))
else (connectedList graph s permanent) fi .
eq unvisitedList nilE permanent = nilE .
eq unvisitedList (t :e graph) permanent = if not(connectedTo (2* t) permanent)
then (t :e (unvisitedList graph permanent))
else (unvisitedList graph permanent) fi .
-- To get the shortest path from a start node to some end node we used the above dijkstra function.
-- From a given start to a given end we need to trace the path from the finish to the start and then reverse the output.
var eList : EdgeList
vars currentTuple : 4Tuple
vars start end : Character
eq SP start end nilE = nilP .
eq SP start end (currentTuple :e eList) = if (end == (1* currentTuple)) then
(end :p (SP start (2* currentTuple) eList))
else (SP start end eList) fi .
-- The graph to be traversed
op DirectedRosetta : -> EdgeList
eq DirectedRosetta = ( << 'a' ; 'b' ; 7 ; inf >> :e
<< 'a' ; 'c' ; 9 ; inf >> :e
<< 'a' ; 'f' ; 14 ; inf >> :e
<< 'b' ; 'c' ; 10 ; inf >> :e
<< 'b' ; 'd' ; 15 ; inf >> :e
<< 'c' ; 'd' ; 11 ; inf >> :e
<< 'c' ; 'f' ; 2 ; inf >> :e
<< 'd' ; 'e' ; 6 ; inf >> :e
<< 'e' ; 'f' ; 9 ; inf >>) .
-- A set of possible starting points
ops oneStart twoStart threeStart fourStart fiveStart sixStart : -> 4Tuple
eq oneStart = << 'a' ; 'a' ; 0 ; 0 >> .
eq twoStart = << 'b' ; 'b' ; 0 ; 0 >> .
eq threeStart = << 'c' ; 'c' ; 0 ; 0 >> .
eq fourStart = << 'd' ; 'd' ; 0 ; 0 >> .
eq fiveStart = << 'e' ; 'e' ; 0 ; 0 >> .
eq sixStart = << 'f' ; 'f' ; 0 ; 0 >> .
} -- End module
-- We must open the module in the CafeOBJ interpreter
open DIJKSTRA .
--> All shortest distances starting from a(1)
red dijkstra 'a' DirectedRosetta oneStart .
-- Gives, where :e is the edge list separator
-- << 'e' ; 'd' ; 6 ; 26 >> :e << 'd' ; 'c' ; 11 ; 20 >> :e << 'f' ; 'c' ; 2 ; 11 >> :e << 'c' ; 'a' ; 9 ; 9 >> :e << 'b' ; 'a' ; 7 ; 7 >>) :e << 'a' ; 'a' ; 0 ; 0 >> :EdgeList
--> Shortest path from a(1) to e(5)
red reverse (SP 'a' 'e' (dijkstra 'a' DirectedRosetta oneStart)) .
-- Gives, where :p is the path list separator
-- 'a' :p 'c' :p 'd' :p 'e' :PathList
--> Shortest path from a(1) to f(6)
red reverse (SP 'a' 'f' (dijkstra 'a' DirectedRosetta oneStart)) .
-- Gives, where :p is the path list separator
-- 'a' :p 'c' :p 'f':PathList
eof
</syntaxhighlight>
=={{header|Clojure}}==
<
(declare neighbours
process-neighbour
Line 1,672 ⟶ 3,014:
;; | e | 26 | (a c d e) |
;; | f | 11 | (a c f) |
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(defparameter *w* '((a (a b . 7) (a c . 9) (a f . 14))
(b (b c . 10) (b d . 15))
Line 1,776 ⟶ 3,038:
(defun nodes (c)
(sort (cdr (assoc c *w*)) #'< :key #'cddr))
</syntaxhighlight>
{{out}}
<pre>
Line 1,782 ⟶ 3,044:
((A C D E) 26)
</pre>
<
(defvar *r* nil)
Line 1,799 ⟶ 3,061:
(paths w b g (+ (cddr a) z)
(cons b v))))))
</syntaxhighlight>
{{out}}
<pre>
Line 1,830 ⟶ 3,092:
{{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 1,912 ⟶ 3,174:
writeln(`Distance from "a" to "e": `, minDistance["e"]);
writeln("Path: ", dijkstraGetShortestPathTo("e", previous));
}</
{{out}}
<pre>Distance from "a" to "e": 26
Line 1,921 ⟶ 3,183:
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,030 ⟶ 3,292:
WriteLn( lineOut);
end;
end.</
{{out}}
<pre>
Line 2,041 ⟶ 3,303:
</pre>
=={{header|
<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">
(
(b c 10)
(b d 15)
(
(c f 2)
(d e 6)
(e f 9)))
(defun calculate-shortest-path (path-list)
(let (shortest-path)
(dolist (path path-list)
(
(nth 1 path)
nil
(nth 2 path))
(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))
(defun find-shortest-route (from to path-list)
(let ((shortest-path-list (calculate-shortest-path path-list))
point-list matched-path distance)
(add-to-list 'point-list to)
(setq matched-path
(seq-find (lambda (path) (equal (list from to) (seq-take path 2)))
shortest-path-list))
(setq distance (nth 3 matched-path))
(while (nth 2 matched-path)
(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
(add-to-list 'point-list from)
(list 'route point-list 'distance distance))
nil)))
(format "%S" (find-shortest-route 'a 'e path-list))
</syntaxhighlight>
outputs:
<pre>
(route (a c d e) distance 26)
</pre>
=={{header|Erlang}}==
<
-module(dijkstra).
-include_lib("eunit/include/eunit.hrl").
Line 2,200 ⟶ 3,502:
io:format(user, "The total cost was ~p and the path was: ", [Cost]),
io:format(user, "~w~n", [Path]).
</syntaxhighlight>
{{out}}
Line 2,215 ⟶ 3,517:
=={{header|F_Sharp|F#}}==
===Dijkstra's algorithm===
<
//Dijkstra's algorithm: Nigel Galloway, August 5th., 2018
[<CustomEquality;CustomComparison>]
Line 2,243 ⟶ 3,545:
|_ ->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,252 ⟶ 3,554:
printfn "%A" (paths E)
printfn "%A" (paths F)
</syntaxhighlight>
{{out}}
<pre>
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>
=={{header|Go}}==
<
import (
Line 2,422 ⟶ 4,193:
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,434 ⟶ 4,205:
{{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,492 ⟶ 4,263:
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,624 ⟶ 4,395:
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,648 ⟶ 4,419:
discovered and then outputs the shortest path.
<
graph := getGraph()
repeat {
Line 2,756 ⟶ 4,527:
procedure waitForCompletion()
critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)
end</
Sample run:
Line 2,790 ⟶ 4,561:
=={{header|J}}==
<syntaxhighlight lang="j">
NB. verbs and adverb
parse_table=: ;:@:(LF&= [;._2 -.&CR)
mp=:
min=: <./ NB. minimum
Index=: (i.`)(`:6) NB. Index adverb
Line 2,865 ⟶ 4,636:
5 3 9
)
</syntaxhighlight>
=== J: Alternative Implementation ===
<
edges=:|: ;:;._2]0 :0
a b 7
Line 2,911 ⟶ 4,682:
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 2,932 ⟶ 4,703:
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,092 ⟶ 4,863:
}
}
}</
a -> c(9) -> d(20) -> e(26)
</pre>
Line 3,098 ⟶ 4,869:
=={{header|Javascript}}==
Using the [[wp:Dijkstra's_algorithm#Pseudocode]]
<
const dijkstra = (edges,source,target) => {
const Q = new Set(),
Line 3,184 ⟶ 4,955:
console.log(path) //[ 'a', 'c', 'f', 'e' ]
console.log(length) //20
</syntaxhighlight>
=={{header|jq}}==
Line 3,202 ⟶ 4,973:
'''Preliminaries'''
<
# def keys_unsorted: keys;
Line 3,271 ⟶ 5,042:
| readout($endname) ;
</syntaxhighlight>
'''The Task'''
<
"a": {"b": 7, "c": 9, "f": 14},
"b": {"c": 10, "d": 15},
Line 3,285 ⟶ 5,056:
"\nThe shortest paths from a to e and to f:",
(GRAPH | Dijkstra("a"; "e", "f") | .[0])</
{{out}}
<pre>
Line 3,295 ⟶ 5,066:
=={{header|Julia}}==
{{works with|Julia|
<syntaxhighlight lang
struct Digraph{T <: Real,U}
edges::Dict{Tuple{U,U},T}
verts::Set{U}
Line 3,346 ⟶ 5,119:
else
while dest != source
dest = prev[dest]
end
return rst, cost
end
Line 3,355 ⟶ 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 3,415 ⟶ 5,191:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.TreeSet
Line 3,561 ⟶ 5,337:
printPath(END)
}
}</
{{out}}
Line 3,572 ⟶ 5,348:
=={{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,638 ⟶ 5,414:
-- 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,644 ⟶ 5,420:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Dijkstra`s_algorithm {
const max_number=1.E+306
Line 3,732 ⟶ 5,508:
}
Dijkstra`s_algorithm
</syntaxhighlight>
{{out}}
Line 3,788 ⟶ 5,564:
=={{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 3,805 ⟶ 5,581:
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 3,822 ⟶ 5,598:
shortest_weighted_path(1, 5, g);
/* [26, [1, 3, 4, 5]] */</
=={{header|Nim}}==
Translation of Wikipedia pseudo-code.
<syntaxhighlight lang="nim">
# Dijkstra algorithm.
Line 3,906 ⟶ 5,682:
printPath(graph.dijkstraPath("a", "e"))
printPath(graph.dijkstraPath("a", "f"))
</syntaxhighlight>
{{out}}
<pre>
Line 3,917 ⟶ 5,693:
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,003 ⟶ 5,779:
in
let p = dijkstra max_int 0 (+) graph "a" "e" in
print_endline (String.concat " -> " p)</
Output:
Line 4,011 ⟶ 5,787:
{{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,066 ⟶ 5,842:
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,088 ⟶ 5,864:
);
dist
};</
=={{header|Pascal}}==
Classic algorithm like this has to have a Pascal implementation...
<
type
Line 4,254 ⟶ 6,030:
vtx := vtx^.next;
end
end.</
{{Out}}
Line 4,275 ⟶ 6,051:
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,383 ⟶ 6,159:
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Line 4,395 ⟶ 6,171:
=={{header|Perl}}==
<
use warnings;
use constant True => 1;
Line 4,457 ⟶ 6,233:
}
my $path = join '', reverse @a;
print "$g->{e}{dist} $path\n";</
{{out}}
<pre>26 acde</pre>
Line 4,465 ⟶ 6,241:
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,551 ⟶ 6,327:
<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,561 ⟶ 6,337:
=={{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,631 ⟶ 6,407:
echo "path is: ".implode(", ", $path)."\n";
</syntaxhighlight>
Output is:
<pre>path is: a, c, f, e</pre>
Line 4,637 ⟶ 6,413:
=={{header|PicoLisp}}==
Following the Wikipedia algorithm:
<
(push (prop X 'neighbors) (cons Y Cost))
(push (prop Y 'neighbors) (cons X Cost)) )
Line 4,654 ⟶ 6,430:
(del (asoq Curr (: neighbors)) (:: neighbors)) ) )
(setq Curr Next Cost Min) ) )
Cost ) )</
Test:
<
(neighbor 'a 'c 9)
(neighbor 'a 'f 14)
Line 4,666 ⟶ 6,442:
(neighbor 'e 'f 9)
(dijkstra 'a 'e)</
Output:
<pre>-> 20</pre>
Line 4,715 ⟶ 6,491:
<
:-dynamic
Line 4,761 ⟶ 6,537:
[Path, Dist, Distance]);
writef('There is no route from %w to %w\n', [From, To]).
</syntaxhighlight>
for example:
<pre>?- go(a,e).
Line 4,784 ⟶ 6,560:
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 4,833 ⟶ 6,609:
("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),
("e", "f", 9)])
pp(graph.dijkstra("a", "e"))</
{{out}}
Line 4,839 ⟶ 6,615:
=={{header|Racket}}==
<
#lang racket
(require (planet jaymccarthy/dijkstra:1:2))
Line 4,862 ⟶ 6,638:
(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 4,951 ⟶ 6,727:
["d", "e", 6],
["e", "f", 9]
]).dijkstra('a', 'e').say;</
{{out}}
<pre>
Line 4,962 ⟶ 6,738:
:::* 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,017 ⟶ 6,793:
@.?= !.qq; call .path ?+1 /*recursive call for next path. */
end /*qq*/
return</
{{out|output|text= when using the internal default inputs:}}
<pre>
Line 5,037 ⟶ 6,813:
=={{header|Ring}}==
<
# Project : Dijkstra's algorithm
Line 5,115 ⟶ 6,891:
dgraph[p] = s
next
</syntaxhighlight>
Output:
<pre>
Line 5,127 ⟶ 6,903:
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,197 ⟶ 6,973:
path, dist = g.shortest_path(start, stop)
puts "shortest path from #{start} to #{stop} has cost #{dist}:"
puts path.join(" -> ")</
{{out}}
Line 5,206 ⟶ 6,982:
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,324 ⟶ 7,100:
println!("\nCost: {}", cost);
}</
{{out}}
<pre>
Line 5,333 ⟶ 7,109:
=={{header|SAS}}==
Use network solver in SAS/OR:
<
data Edges;
input Start $ End $ Cost;
Line 5,370 ⟶ 7,146:
/* print shortest path */
proc print data=path;
run;</
Output:
Line 5,383 ⟶ 7,159:
A functional implementation of Dijkstras Algorithm:
<
type Path[Key] = (Double, List[Key])
Line 5,411 ⟶ 7,187:
println(res)
}
}</
{{out}}
Line 5,419 ⟶ 7,195:
An implementation based on the functional version above that uses <code>PriorityQueue</code>. It is made functional-look:
<
import scala.collection.mutable
Line 5,477 ⟶ 7,253:
}
}
</syntaxhighlight>
{{out}}
<pre>(26.0,List(a, c, d, e))</pre>
Line 5,483 ⟶ 7,259:
=={{header|Sidef}}==
{{trans|Perl}}
<
struct Node {
Line 5,573 ⟶ 7,349:
var path = a.reverse.join
say "#{g.get('e').dist} #{path}"</
{{out}}
<pre>
Line 5,585 ⟶ 7,361:
{{trans|Rust}}
<
struct Grid<T> {
Line 5,673 ⟶ 7,449:
print("Cost: \(cost)")
print(path.map({ grid.nodes[$0].data }).joined(separator: " -> "))</
{{out}}
Line 5,682 ⟶ 7,458:
=={{header|Tailspin}}==
A simple algorithm that traverses through all edges at every step.
<
data vertex <'a'..'f'>, to <vertex>
Line 5,716 ⟶ 7,492:
$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,738 ⟶ 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>
{{out}}
<pre>
Line 5,772 ⟶ 7,548:
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 5,809 ⟶ 7,585:
}
return [list $dist $path]
}</
Showing the code in use:
<
# Assume that all nodes are connected to something
foreach arc $arcs {
Line 5,826 ⟶ 7,602:
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 5,832 ⟶ 7,608:
route from a to e is: a -> c -> f -> e
</pre>
=={{header|Wren}}==
Line 6,018 ⟶ 7,615:
{{libheader|Wren-sort}}
{{libheader|Wren-set}}
<
import "./trait" for Comparable
import "./sort" for Cmp, Sort
import "./set" for Set
var Edge = Tuple.create("Edge", ["v1", "v2", "dist"])
Line 6,169 ⟶ 7,766:
g = Graph.new(GRAPH, false, false) // undirected
g.dijkstra(START)
g.printPath(END)</
{{out}}
Line 6,179 ⟶ 7,776:
=={{header|zkl}}==
<
fcn dijkstra(graph,start,dst){
Q :=graph.copy();
Line 6,200 ⟶ 7,797:
}
}
}</
<
"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,210 ⟶ 7,807:
);
dijkstra(graph,"a","e").println();
dijkstra(graph,"e","a").println();</
{{out}}
<pre>
| |||