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:
* elimination of duplications (the cheapest path is chosen)
* a test for a ''no path found'' condition
<lang rexx>/*REXX pgm finds the least costly path between two2 vertices given a list.*/
numeric digits 20 /*must be >≥ than any path cost.*/
$.=copies(9,digits()) /*edge cost; this means not¬ exist.*/
aList='!. @. $. beg fin bestP best$ xx yy' /*"common" variables.*/
@abc='abcdefghijklmnopqrstuvwxyz' /*list of possible vertices. */
verts=0 /*number of vertices. */
edges=0 /*number of edges. */
do jj=1 for length(@abc); _=substr(@abc,jj,1)
call value translate(_),jj; @@.jj=_
end /*jj*/
Line 1,099:
call def$ d e 6 /*define an edge and its cost. */
call def$ e f 9 /*define an edge and its cost. */
finbeg=ea /*the finishbegin vertix vertex. */▼
say
begfin=ae /*the beginfinish vertixvertex. */
say; say 'number of edges = ' edges
▲fin=e /*the finish vertix. */
say 'number of vertices = ' edgesverts " = ' edges["left(@abc,verts)"]"
say 'number of vertices = ' verts " ["left(@abc,verts)"]"
best$=$.; bestP=
do jv=2 to verts
call paths verts,jv
end /*jv*/
say
if bestP==$. then do; say 'no path found.'; exit; end /*oops-ay. */
say 'best path =' translate(bestP,@abc,123456789) ' cost =' best$
exit /*stick a fork in it, we're done.*/
Line 1,115 ⟶ 1,114:
apath: parse arg pathx 1 p1 2 p2 3; Lp=length(pathx); $=$.p1.p2
if $>=best$ then return
pv=p2; do ka=3 to Lp; cp _=substr(pathx,ka,1)
if $.pv.cp_>=best$ then return
$=$+$.pv.cp_; if $>=best$ then return
pv=cp_
end /*kkka*/
best$=$; bestP=pathx
return
/*──────────────────────────────────DEF$──────────────────────────────── subroutine─────────────────────*/
def$: parse arg xx yy $ .; if $.xx.yy<$ & $.yy.xx<$ | xx=yy then return
edges=edges+1; verts=verts + ($.xx\==0) + ($.yy\==0)
$.xx=0; $.yy=0; $.xx.yy=$; $.yy.xx=$
say left('',40) "cost of " @@.xx '◄───►' @@.yy " is " $
return
/*──────────────────────────────────PATHS subroutine────────────────────*/
paths: procedure expose (aList); parse arg xx,yy,@.
do kp=1 for xx; _=kp; !.kp=_ /*build path list.*/
end /*kp*/
call .paths 1
return
/*──────────────────────────────────.PATHS subroutine───────────────────*/
.paths: procedure expose (aList); parse arg ?,_
if ?>yy then do; if @.1\==beg then return; if @.yy\==fin then return
if do jj@.1\=1=beg for| @.yy; _\=_||@.jj; end; call apath=fin _;then endreturn
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 /*kjj*/
@.?=!.qq; call .pathsapath ?+1_
end /*qq*/
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>
'''output''' when using the input of: <tt> xxx </tt>
Retrieved from "https://rosettacode.org/wiki/Dijkstra%27s_algorithm"