Dijkstra's algorithm: Difference between revisions
m
→{{header|EasyLang}}
Drkameleon (talk | contribs) |
|||
| (12 intermediate revisions by 8 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][]
Line 1,746 ⟶ 1,684:
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,757 ⟶ 3,015:
;; | f | 11 | (a c f) |
</syntaxhighlight>
=={{header|Common Lisp}}==
Line 3,124 ⟶ 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 3,226 ⟶ 3,451:
<pre>
(route (a c d e) distance 26)
</pre>
Line 3,341 ⟶ 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>
Line 4,032 ⟶ 4,564:
NB. verbs and adverb
parse_table=: ;:@:(LF&= [;._2 -.&CR)
mp=:
min=: <./ NB. minimum
Index=: (i.`)(`:6) NB. Index adverb
Line 6,982 ⟶ 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 7,076 ⟶ 7,608:
route from a to e is: a -> c -> f -> e
</pre>
=={{header|Wren}}==
Line 7,262 ⟶ 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"])
| |||