133 lines
2.6 KiB
Plaintext
133 lines
2.6 KiB
Plaintext
Module Dijkstra`s_algorithm {
|
|
const max_number=1.E+306
|
|
GetArr=lambda (n, val)->{
|
|
dim d(n)=val
|
|
=d()
|
|
}
|
|
FillList=lambda (n) -> {
|
|
m=list
|
|
for i=1 to n : append m, i :next
|
|
=m
|
|
}
|
|
// tree
|
|
class node {
|
|
name$, val as long
|
|
remove {
|
|
created--
|
|
print "Node removed, left: "+created
|
|
}
|
|
class:
|
|
module node (.name$, .val) {
|
|
created++
|
|
print "New node, total: "+created
|
|
}
|
|
}
|
|
global long created
|
|
pNode = lambda ->{
|
|
->node(![])
|
|
}
|
|
Class EdgeList {
|
|
object Node[0]
|
|
name$
|
|
class:
|
|
module EdgeList (.name$) {
|
|
n=0
|
|
while not empty
|
|
read .Node[n]
|
|
n++
|
|
end while
|
|
}
|
|
}
|
|
Node_A=EdgeList("a", pNode("b",7), pNode("c", 9), pNode("f",14) )
|
|
Node_B=EdgeList("b",pNode("c",10),pNode("d",15))
|
|
Node_C=EdgeList("c",pNode("d",11),pNode("f",2))
|
|
Node_D=EdgeList("d",pNode("e",6))
|
|
Node_E=EdgeList("e",pNode("f", 9))
|
|
Node_F=EdgeList("f",pNode())
|
|
Dim Edges(6)
|
|
Edges(0)=Node_A, Node_B, Node_C, Node_D, Node_E, Node_F
|
|
Document Doc$="Graph:"+{
|
|
}
|
|
ShowGraph()
|
|
Doc$="Paths"+{
|
|
}
|
|
Print "Paths"
|
|
For from_here=0 to Len(Edges())-1
|
|
pa=GetArr(len(Edges()), -1)
|
|
d=GetArr(len(Edges()), max_number)
|
|
S=FillList(len(Edges()))
|
|
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(u-1).node, i
|
|
local e=Len(vertex)-1, val
|
|
for i=0 to e
|
|
for vertex[i] {
|
|
if .name$<>"" then
|
|
val=Asc(.name$)-Asc("a")
|
|
if d#val(val)>.val+d#val(u-1) then return d, val:=.val+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 line$, j
|
|
for Edges(n) {
|
|
for j=0 to len(.node)-1
|
|
Print .name$;
|
|
for .node[j] {
|
|
if ..name$>"" then
|
|
print "->"+..name$+" "+format$(" {0::-2}",..val)
|
|
else
|
|
print
|
|
end if
|
|
}
|
|
next
|
|
}
|
|
end sub
|
|
}
|
|
Dijkstra`s_algorithm
|