Dijkstra's algorithm: Difference between revisions

;An example, starting with:

a──►c, cost=9, lastNode=a

a──►d, cost=NA, lastNode=a

c──►f

a──►c

{{trans|Python}}

String start

String end

(‘b’, ‘d’, 15), (‘c’, ‘d’, 11), (‘c’, ‘f’, 2), (‘d’, ‘e’, 6),

(‘e’, ‘f’, 9)])

{{out}}

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 (<>);

end record;

type t_Graph is array (t_Vertex) of t_Vertex_Data;

package body Dijkstra is

end Distance;

The testing main procedure :

with Dijkstra;

procedure Test_Dijkstra is

end loop;

end loop;

{{out}}

<pre>Path from 'a' to 'e' = [a,c,d,e] distance = 26

{{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''.}}

COMMENT REQUIRED BY "prelude_dijkstras_algorithm.a68" CO

);

# -*- coding: utf-8 -*- #

# TODO: generate random 100000 VERTEX graph test case and test performance - important #

<pre>

a --9-> c --2-> f --9-> e

=={{header|Applesoft BASIC}}==

110 DEF FN N(P) = ASC(MID$(N$,P+(P=0),1))-64

120 DIM D(26),UNVISITED(26)

670 DATA 6,D-E

680 DATA 9,E-F

'''Output:'''

<pre>SHORTEST PATH

{{trans|Nim}}

initGraph: function [edges][

print ["Shortest path from 'a' to 'e': " join.with:" -> " dijkstraPath graph "a" "e"]

{{out}}

=={{header|AutoHotkey}}==

nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"

for each, line in StrSplit(data, "`n" , "`r")

count := A_Index

return count

(

A B 7

GuiClose:

ExitApp

Outputs:<pre>A > C 9

C > F 2

=={{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.

#include <stdio.h>

#include <stdlib.h>

return 0;

}

output

26 acde

=={{header|C sharp|C#}}==

{{works with|C sharp|7}}

using static System.String;

using static System.Console;

}

{{out}}

<pre>

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>

return 0;

----

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>

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.

"

This code works with CafeOBJ 1.5.1 and CafeOBJ 1.5.5.

-- 'a' :p 'c' :p 'f':PathList

eof

=={{header|Clojure}}==

(declare neighbours

process-neighbour

;; | e | 26 | (a c d e) |

;; | f | 11 | (a c f) |

=={{header|Commodore BASIC}}==

(The program outputs the shortest path to each node in the graph, including E and F, so I assume that meets the requirements of Task item 3.)

110 READ N$:IF N$<>"" THEN NV=NV+1:GOTO 110

120 NE=0: REM NUMBER OF EDGES

700 DATA 4,5,9

710 DATA -1

{{Out}}

=={{header|Common Lisp}}==

(defparameter *w* '((a (a b . 7) (a c . 9) (a f . 14))

(b (b c . 10) (b d . 15))

(defun nodes (c)

(sort (cdr (assoc c *w*)) #'< :key #'cddr))

{{out}}

<pre>

((A C D E) 26)

</pre>

(defvar *r* nil)

(paths w b g (+ (cddr a) z)

(cons b v))))))

{{out}}

<pre>

{{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;

writeln(`Distance from "a" to "e": `, minDistance["e"]);

writeln("Path: ", dijkstraGetShortestPathTo("e", previous));

{{out}}

<pre>Distance from "a" to "e": 26

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}

WriteLn( lineOut);

end;

{{out}}

<pre>

=={{header|Emacs Lisp}}==

;; Path format: (start-point end-point previous-point distance)

(setq path-list `(

(calculate-shortest-path)

outputs:

=={{header|Erlang}}==

-module(dijkstra).

-include_lib("eunit/include/eunit.hrl").

io:format(user, "The total cost was ~p and the path was: ", [Cost]),

io:format(user, "~w~n", [Path]).

{{out}}

=={{header|F_Sharp|F#}}==

===Dijkstra's algorithm===

//Dijkstra's algorithm: Nigel Galloway, August 5th., 2018

[<CustomEquality;CustomComparison>]

|_ ->None

fN n [])

===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)]

printfn "%A" (paths E)

printfn "%A" (paths F)

{{out}}

<pre>

=={{header|Go}}==

import (

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}}

{{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

putStrLn $ "Distance from a to e: " ++ show (min_distance ! 'e')

let path = shortest_path_to 'e' ' ' previous

=={{header|Huginn}}==

import Mathematics as math;

import Text as text;

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:

discovered and then outputs the shortest path.

graph := getGraph()

repeat {

procedure waitForCompletion()

critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)

Sample run:

=={{header|J}}==

NB. verbs and adverb

parse_table=: ;:@:(LF&= [;._2 -.&CR)

5 3 9

)

=== J: Alternative Implementation ===

edges=:|: ;:;._2]0 :0

a b 7

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.

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.*;

}

}

a -> c(9) -> d(20) -> e(26)

</pre>

=={{header|Javascript}}==

Using the [[wp:Dijkstra's_algorithm#Pseudocode]]

const dijkstra = (edges,source,target) => {

const Q = new Set(),

console.log(path) //[ 'a', 'c', 'f', 'e' ]

console.log(length) //20

=={{header|jq}}==

'''Preliminaries'''

# def keys_unsorted: keys;

| readout($endname) ;

'''The Task'''

"a": {"b": 7, "c": 9, "f": 14},

"b": {"c": 10, "d": 15},

"\nThe shortest paths from a to e and to f:",

{{out}}

<pre>

{{works with|Julia|0.6}}

edges::Dict{Tuple{U,U},T}

verts::Set{U}

path, cost = dijkstrapath(g, src, dst)

@printf("%4s | %3s | %s\n", src, dst, isempty(path) ? "no possible path" : join(path, " → ") * " ($cost)")

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

import java.util.TreeSet

printPath(END)

}

{{out}}

=={{header|Lua}}==

Hopefully the variable names here make the process as clear as possible...

local edges = {

a = {b = 7, c = 9, f = 14},

-- Main procedure

print("Directed:", dijkstra(edges, "a", "e", true))

{{out}}

<pre>Directed: 26 a c d e

=={{header|M2000 Interpreter}}==

Module Dijkstra`s_algorithm {

const max_number=1.E+306

}

Dijkstra`s_algorithm

{{out}}

=={{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);

=={{header|Mathematica}}/{{header|Wolfram Language}}==

"b" \[DirectedEdge] "c", "b" \[DirectedEdge] "d",

"c" \[DirectedEdge] "d", "d" \[DirectedEdge] "e",

FindShortestPath[bd, "a", "e", Method -> "Dijkstra"]

[[File:Mma_dijkstra2.PNG]]

=={{header|Maxima}}==

g: create_graph([[1, "a"], [2, "b"], [3, "c"], [4, "d"], [5, "e"], [6, "f"]],

[[[1, 2], 7],

shortest_weighted_path(1, 5, g);

=={{header|Nim}}==

Translation of Wikipedia pseudo-code.

# Dijkstra algorithm.

printPath(graph.dijkstraPath("a", "e"))

printPath(graph.dijkstraPath("a", "f"))

{{out}}

<pre>

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

in

let p = dijkstra max_int 0 (+) graph "a" "e" in

Output:

{{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

print_string "Path: ";

List.iter (Printf.printf "%d, ") path;

=={{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;

);

dist

=={{header|Pascal}}==

Classic algorithm like this has to have a Pascal implementation...

type

vtx := vtx^.next;

end

{{Out}}

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.

end;

end.

{{out}}

<pre>

=={{header|Perl}}==

use warnings;

use constant True => 1;

}

my $path = join '', reverse @a;

{{out}}

<pre>26 acde</pre>

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)

<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>

=={{header|PHP}}==

There are parts of this algorithm that could be optimized which have been marked TODO.

<?php

function dijkstra($graph_array, $source, $target) {

echo "path is: ".implode(", ", $path)."\n";

Output is:

<pre>path is: a, c, f, e</pre>

=={{header|PicoLisp}}==

Following the Wikipedia algorithm:

(push (prop X 'neighbors) (cons Y Cost))

(push (prop Y 'neighbors) (cons X Cost)) )

(del (asoq Curr (: neighbors)) (:: neighbors)) ) )

(setq Curr Next Cost Min) ) )

Test:

(neighbor 'a 'c 9)

(neighbor 'a 'f 14)

(neighbor 'e 'f 9)

Output:

<pre>-> 20</pre>

:-dynamic

[Path, Dist, Distance]);

writef('There is no route from %w to %w\n', [From, To]).

for example:

<pre>?- go(a,e).

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

("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),

("e", "f", 9)])

{{out}}

=={{header|Racket}}==

#lang racket

(require (planet jaymccarthy/dijkstra:1:2))

(cond [(eq? (first path) 'a) path]

[(loop (cons (hash-ref prevs (first path)) path))]))))])

Output:

Distances from a: ((b 7) (d 20) (a 0) (c 9) (f 11) (e 26))

Shortest path: (a c d e)

=={{header|Raku}}==

(formerly Perl 6)

{{Works with|Rakudo|2018.03}}

has (%.edges, %.nodes);

["d", "e", 6],

["e", "f", 9]

{{out}}

<pre>

:::* &nbsp; a test for a &nbsp; ''no path found'' &nbsp; condition

:::* &nbsp; use of memoization

$.= copies(9, digits() ) /*edge cost: indicates doesn't exist. */

xList= '!. @. $. beg fin bestP best$ xx yy' /*common EXPOSEd variables for subs. */

@.?= !.qq; call .path ?+1 /*recursive call for next path. */

end /*qq*/

{{out|output|text=&nbsp; when using the internal default inputs:}}

<pre>

=={{header|Ring}}==

# Project : Dijkstra's algorithm

dgraph[p] = s

next

Output:

<pre>

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)

path, dist = g.shortest_path(start, stop)

puts "shortest path from #{start} to #{stop} has cost #{dist}:"

{{out}}

This solution uses a very bare-bones, naive implementation of an adjacency list to represent the graph.

use std::collections::BinaryHeap;

use std::usize;

println!("\nCost: {}", cost);

{{out}}

<pre>

=={{header|SAS}}==

Use network solver in SAS/OR:

data Edges;

input Start $ End $ Cost;

/* print shortest path */

proc print data=path;

Output:

A functional implementation of Dijkstras Algorithm:

type Path[Key] = (Double, List[Key])

println(res)

}

{{out}}

An implementation based on the functional version above that uses <code>PriorityQueue</code>. It is made functional-look:

import scala.collection.mutable

}

}

{{out}}

<pre>(26.0,List(a, c, d, e))</pre>

=={{header|Sidef}}==

{{trans|Perl}}

struct Node {

var path = a.reverse.join

{{out}}

<pre>

{{trans|Rust}}

struct Grid<T> {

print("Cost: \(cost)")

{{out}}

=={{header|Tailspin}}==

A simple algorithm that traverses through all edges at every step.

data vertex <'a'..'f'>, to <vertex>

$fromA... -> \(<{to:<=vertex´'f'>}> $!\) -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);

' -> !OUT::write

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]>

($fromA matching {|{to:'f'}|})... -> 'Shortest path from $.path(1); to $.to; is distance $.distance; via $.path(2..last);

' -> !OUT::write

{{out}}

<pre>

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 {

}

return [list $dist $path]

Showing the code in use:

# Assume that all nodes are connected to something

foreach arc $arcs {

lassign [dijkstra [makeUndirectedGraph $arcs] "a"] costs path

puts "path from a to e costs [dict get $costs e]"

Output:

<pre>

=={{header|VBA}}==

Public from As Node '[according to Dijkstra the first Node should be closest to P]

Public towards As Node

Dijkstra testNodes, testBranches, a

GetPath f

a e 26 a c d e

a f 11 a c f</pre>

{{libheader|Wren-sort}}

{{libheader|Wren-set}}

import "/trait" for Comparable

import "/sort" for Cmp, Sort

g = Graph.new(GRAPH, false, false) // undirected

g.dijkstra(START)

{{out}}

=={{header|zkl}}==

fcn dijkstra(graph,start,dst){

Q :=graph.copy();

}

}

"a", T(T("b", 7.0), T("c", 9.0), T("f",14.0)),

"b", T(T("c",10.0), T("d",15.0)),

);

dijkstra(graph,"a","e").println();

{{out}}

<pre>