## Σάββατο, 27 Απριλίου 2019

### Dijkstra's algorithm

The graph stored in a jagged array. A tuple in m2000 is an array of one dimension. We can put tuple in a tuple too, so this is a jagged array. When we store an array in an array, we store only the pointer to array (which is an object, so we can read the type if we wish).

So Edges is a pointer to the graph (which we didn't change values). The task want only to find the path from a to e, and the weight. But here we search all the paths from every vertex to every vertex (and if not possible the a "no path" label printed).

I use an inventory list only with keys, because we can delete any of them without cost (this list need unique keys). Because we have the statement Inventory in a loop, the second time the inventory must be empty (or an exception produced), but algorithm end when inventory is empty. (to clear an inventory S we have to use Clear S.

There are two lambda functions inside loop. Because we use closures, and for d and pa we get new pointer in each iteration we have to redefine the lambdas to get new closures (with new pointers). Closures in lambda are copies, and this include pointers.

Also I use some subs, which have same scope as the module where we call them. Functions and Modules are namespaces (this include the lambda functions). There is special call to place the same namespace the Call Local but here not used.

I use this pdf for information about algorithm.

```Module Dijkstra`s_algorithm {
const max_number=1.E+306
GetArr=lambda (n, val)->{
dim d(n)=val
=d()
}
term=("",0)
Edges=(("a", ("b",7),("c",9),("f",14)),("b",("c",10),("d",15)),("c",("d",11),("f",2)),("d",("e",6)),("e",("f", 9)),("f",term))
Document Doc\$="Graph:"+{
}
ShowGraph()
Doc\$="Paths"+{
}
Print "Paths"
For from_here=0 to 5
pa=GetArr(len(Edges), -1)
d=GetArr(len(Edges), max_number)
Inventory S=1,2,3,4,5,6
return d, from_here:=0
RemoveMin=Lambda S, d, max_number-> {
ss=each(S)
min=max_number
p=0
while ss
val=d#val(eval(S,ss^)-1)
if min>val then let min=val : p=ss^
end while
=s(p!)  ' use p as index not key
Delete S, eval(s,p)
}
Show_Distance_and_Path\$=lambda\$ d, pa, from_here, max_number (n) -> {
ret1\$=chr\$(from_here+asc("a"))+" to "+chr\$(n+asc("a"))
if d#val(n) =max_number then =ret1\$+ "No Path" :exit
let ret\$="", mm=n, m=n
repeat
n=m
ret\$+=chr\$(asc("a")+n)
m=pa#val(n)
until  from_here=n
=ret1\$+format\$("{0::-4} {1}",d#val(mm),strrev\$(ret\$))
}
while len(s)>0
u=RemoveMin()
rem Print u, chr\$(u-1+asc("a"))
Relaxed()
end while
For i=0 to len(d)-1
line\$=Show_Distance_and_Path\$(i)
Print line\$
doc\$=line\$+{
}
next
next
Clipboard Doc\$
End
Sub Relaxed()
local vertex=Edges#val(u-1), i
local e=Len(vertex)-1, edge=(,), val
for i=1 to e
edge=vertex#val(i)
if edge#val\$(0)<>"" then
val=Asc(edge#val\$(0))-Asc("a")
if d#val(val)>edge#val(1)+d#val(u-1) then  return d, val:=edge#val(1)+d#val(u-1) : Return Pa, val:=u-1
end if
next
end sub
Sub ShowGraph()
Print "Graph"
local i
for i=1 to len(Edges)
show_edges(i)
next
end sub
Sub show_edges(n)
n--
local vertex=Edges#val(n), line\$
local e=each(vertex 2 to end), v2=(,)
While e
v2=array(e)
line\$=vertex#val\$(0)+if\$(v2#val\$(0)<>""->"->"+v2#val\$(0)+format\$(" {0::-2}",v2#val(1)),"")
Print line\$
Doc\$=line\$+{
}
end while
end sub
}
Dijkstra`s_algorithm```

Graph:
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
f
Paths
a to a   0 a
a to b   7 ab
a to c   9 ac
a to d  20 acd
a to e  26 acde
a to f  11 acf
b to a     No Path
b to b   0 b
b to c  10 bc
b to d  15 bd
b to e  21 bde
b to f  12 bcf
c to a     No Path
c to b     No Path
c to c   0 c
c to d  11 cd
c to e  17 cde
c to f   2 cf
d to a     No Path
d to b     No Path
d to c     No Path
d to d   0 d
d to e   6 de
d to f  15 def
e to a     No Path
e to b     No Path
e to c     No Path
e to d     No Path
e to e   0 e
e to f   9 ef
f to a     No Path
f to b     No Path
f to c     No Path
f to d     No Path
f to e     No Path
f to f   0 f