Dijkstra's algorithm: Difference between revisions

Content added Content deleted
(→‎{{header|OCaml}}: added translation from c++)
m (→‎{{header|REXX}}: corrected comments and DO-END comment labels, changed indentation, simplified logic, added whitespace. -- ~~~~)
Line 1,080: Line 1,080:
* elimination of duplications (the cheapest path is chosen)
* elimination of duplications (the cheapest path is chosen)
* a test for a ''no path found'' condition
* a test for a ''no path found'' condition
<lang rexx>/*REXX pgm finds the least costly path between two vertices given a list*/
<lang rexx>/*REXX pgm finds the least costly path between 2 vertices given a list.*/
numeric digits 20 /*must be > than any path cost.*/
numeric digits 20 /*must be ≥ than any path cost.*/
$.=copies(9,digits()) /*edge cost; this means not exist*/
$.=copies(9,digits()) /*edge cost; this means ¬ exist.*/
aList='!. @. $. beg fin bestP best$ xx yy' /*"common" variables.*/
aList='!. @. $. beg fin bestP best$ xx yy' /*"common" variables.*/
@abc='abcdefghijklmnopqrstuvwxyz' /*list of possible vertices. */
@abc='abcdefghijklmnopqrstuvwxyz' /*list of possible vertices. */
verts=0 /*number of vertices. */
verts=0 /*number of vertices. */
edges=0 /*number of edges. */
edges=0 /*number of edges. */
do jj=1 for length(@abc); _=substr(@abc,jj,1)
do jj=1 for length(@abc); _=substr(@abc,jj,1)
call value translate(_),jj; @@.jj=_
call value translate(_),jj; @@.jj=_
end /*jj*/
end /*jj*/
Line 1,099: Line 1,099:
call def$ d e 6 /*define an edge and its cost. */
call def$ d e 6 /*define an edge and its cost. */
call def$ e f 9 /*define an edge and its cost. */
call def$ e f 9 /*define an edge and its cost. */
⚫
beg=a /*the begin vertex. */
say
beg=a /*the begin vertix. */
fin=e /*the finish vertex. */
say; say 'number of edges = ' edges
⚫
fin=e /*the finish vertix. */
say 'number of edges = ' edges
say 'number of vertices = ' verts " ["left(@abc,verts)"]"
say 'number of vertices = ' verts " ["left(@abc,verts)"]"
best$=$.; bestP=
best$=$.; bestP=
do jv=2 to verts
do jv=2 to verts
call paths verts,jv
call paths verts,jv
end /*jv*/
end /*jv*/
say
say
if bestP==$. then do; say 'no path found.'; exit; end /*oops-ay. */
if bestP==$. then do; say 'no path found.'; exit; end /*oops-ay. */
say 'best path =' translate(bestP,@abc,123456789) ' cost =' best$
say 'best path =' translate(bestP,@abc,123456789) ' cost =' best$
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're done.*/
Line 1,115: Line 1,114:
apath: parse arg pathx 1 p1 2 p2 3; Lp=length(pathx); $=$.p1.p2
apath: parse arg pathx 1 p1 2 p2 3; Lp=length(pathx); $=$.p1.p2
if $>=best$ then return
if $>=best$ then return
pv=p2; do ka=3 to Lp; cp=substr(pathx,ka,1)
pv=p2; do ka=3 to Lp; _=substr(pathx,ka,1)
if $.pv.cp>=best$ then return
if $.pv._>=best$ then return
$=$+$.pv.cp; if $>=best$ then return
$=$+$.pv._; if $>=best$ then return
pv=cp
pv=_
end /*kk*/
end /*ka*/
best$=$; bestP=pathx
best$=$; bestP=pathx
return
return
/*──────────────────────────────────DEF$────────────────────────────────*/
/*──────────────────────────────────DEF$ subroutine─────────────────────*/
def$: parse arg xx yy $ .; if $.xx.yy<$ & $.yy.xx<$ | xx=yy then return
def$: parse arg xx yy $ .; if $.xx.yy<$ & $.yy.xx<$ | xx=yy then return
edges=edges+1; verts=verts+($.xx\==0)+($.yy\==0)
edges=edges+1; verts=verts + ($.xx\==0) + ($.yy\==0)
$.xx=0; $.yy=0; $.xx.yy=$; $.yy.xx=$
$.xx=0; $.yy=0; $.xx.yy=$; $.yy.xx=$
say left('',40) "cost of " @@.xx '◄───►' @@.yy " is " $
say left('',40) "cost of " @@.xx '◄───►' @@.yy " is " $
return
return
/*──────────────────────────────────PATHS subroutine────────────────────*/
/*──────────────────────────────────PATHS subroutine────────────────────*/
paths: procedure expose (aList); parse arg xx,yy,@.
paths: procedure expose (aList); parse arg xx,yy,@.
do kp=1 for xx; _=kp; !.kp=_ /*build path list.*/
do kp=1 for xx; _=kp; !.kp=_ /*build path list.*/
end /*kp*/
end /*kp*/
call .paths 1
call .paths 1
return
return
/*──────────────────────────────────.PATHS subroutine───────────────────*/
/*──────────────────────────────────.PATHS subroutine───────────────────*/
.paths: procedure expose (aList); parse arg ?,_
.paths: procedure expose (aList); parse arg ?,_
if ?>yy then do; if @.1\==beg then return; if @.yy\==fin then return
if ?>yy then do
do jj=1 for yy; _=_||@.jj; end; call apath _; end
if @.1\==beg | @.yy\==fin then return
else do qq=1 for xx /*build vertix paths recursively.*/
do jj=1 for yy; _=_||@.jj
do kp=1 for ?-1; if @.kp==!.qq then iterate qq; end /*k*/
end /*jj*/
@.?=!.qq; call .paths ?+1
call apath _
end /*qq*/
end
else do qq=1 for xx /*build vertex paths recursively.*/
do kp=1 for ?-1
if @.kp==!.qq then iterate qq
end /*kp*/
@.?=!.qq; call .paths ?+1
end /*qq*/
return</lang>
return</lang>
'''output''' when using the input of: <tt> xxx </tt>
'''output''' when using the input of: <tt> xxx </tt>
Retrieved from "https://rosettacode.org/wiki/Dijkstra%27s_algorithm"