(phixonline)-->
with javascript_semantics
--requires("1.0.2") -- (builtin E renamed as EULER)
--enum A,B,C,D,E,F
constant A=1, B=2, C=3, D=4, E=5, F=6 -- (or use this)
constant edges = {{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}}
sequence visited,
cost,
from
procedure reset()
visited = repeat(0,6)
cost = repeat(0,6)
from = repeat(0,6)
end procedure
function backtrack(integer finish,start)
sequence res = {finish}
while finish!=start do
finish = from[finish]
res = prepend(res,finish)
end while
return res
end function
function shortest_path(integer start, integer finish)
integer estart, eend, ecost, ncost, mincost
while 1 do
visited[start] = 1
for i=1 to length(edges) do
{estart,eend,ecost} = edges[i]
if estart=start then
ncost = cost[start]+ecost
if visited[eend]=0 then
if from[eend]=0
or cost[eend]>ncost then
cost[eend] = ncost
from[eend] = start
end if
elsif cost[eend]>ncost then
?9/0 -- sanity check
end if
end if
end for
mincost = 0
for i=1 to length(visited) do
if visited[i]=0
and from[i]!=0 then
if mincost=0
or cost[i]<mincost then
start = i
mincost = cost[start]
end if
end if
end for
if visited[start] then return -1 end if
if start=finish then return cost[finish] end if
end while
end function
function AFi(integer i) -- output helper
return 'A'+i-1
end function
procedure test(sequence testset)
integer start, finish, ecost, len
string epath, path
for i=1 to length(testset) do
{start,finish,ecost,epath} = testset[i]
reset()
len = shortest_path(start,finish)
path = iff(len=-1?"no path found":join(apply(backtrack(finish,start),AFi),""))
printf(1,"%c->%c: length %d:%s (expected %d:%s)\n",{AFi(start),AFi(finish),len,path,ecost,epath})
end for
end procedure
test({{A,E,26,"ACDE"},{A,F,11,"ACF"},{F,A,-1,"none"}})