#C2.txt: Jan. 27, 2025
Help2:=proc(): print(`LC(p), RG(n,p)  `):end:

Help18:=proc(): print(` RWG(n,p,K), Dij( [4, {{1, 2}, {1, 3}, {2, 3}, {3, 4}}, table([{3, 4} = 2, {1, 2} = 2, {1, 3} = 3, {2, 3} = 2])]  ,1);  `):
print(`  DijP( [4, {{1, 2}, {1, 3}, {2, 3}, {3, 4}}, table([{3, 4} = 2, {1, 2} = 2, {1, 3} = 3, {2, 3} = 2])]  ,1);  `):end:





#From C2.txt
with(combinat):
#LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p
LC:=proc(p) local a,b,ra:
if not (type(p,fraction) and p>=0 and p<=1) then
 RETURN(FAIL):
fi:
a:=numer(p):
b:=denom(p):
ra:=rand(1..b)():
if ra<=a then
 true:
else
 false:
fi:
end:

RG:=proc(n,p) local E,i,j:
E:={}:
for i from 1 to n do
 for j from i+1 to n do
   if LC(p) then
    E:=E union {{i,j}}:
   fi:
 od:
od:
[n,E]:
end:

##end from C2.txt

#RWG(n,p,K): a random un-weighted graph with prob. of an edge p and a weight from 1 to K
RWG:=proc(n,p,K) local ra,G,T,e,E:
G:=RG(n,p):
E:=G[2]:

ra:=rand(1..K):

for e  in E do
 T[e]:=ra():
od:

[n,E,op(T)]:
end:

#Dij(G,a): inputs a weighted graph [n,E,DistanceTable] outputs a list of length n,L,  such that L[i] is the shortest distance from a to i.
#Try:
#Dij([3,{{1,2},{1,3}},table([{2, 3} = 5, {1, 3} = 1, {1, 2} = 3]));
Dij:=proc(G,a) local n,E,DT,i,N,e,T,UnVis,Vis,v,cha,rec,Nei,Tt,cu,i1:
n:=G[1]:
E:=G[2]:
DT:=G[3]:

for i from 1 to n do
 N[i]:={}:
od:

for e in E do
N[e[1]]:=N[e[1]] union {e[2]}:
N[e[2]]:=N[e[2]] union {e[1]}:
od:

UnVis:={seq(i,i=1..n)}:

for i from 1 to n do
Tt[i]:=infinity:
od:
Vis:=[a]:
UnVis:=UnVis minus {a}:

T[a]:=0:
while UnVis<>{} do
cu:=Vis[-1]:
Nei:=N[cu]:

for v in Nei do
 Tt[v]:=min(Tt[v],T[cu]+DT[{cu,v}]):
od:

cha:=UnVis[1]:
rec:=Tt[cha]:

for i1 from 2 to nops(UnVis) do
 if Tt[UnVis[i1]]<rec then
   cha:=UnVis[i1]:
   rec:=Tt[cha]:
 fi:
od:
Vis:=[op(Vis),cha]:
T[cha]:=rec:
UnVis:=UnVis minus {cha}:
od:
  
[seq(T[i],i=1..n)]:


end:


#DijP(G,a): inputs a weighted graph [n,E,DistanceTable] outputs a list of length n,L,  such that L[i] is the shortest distance from a to i.
#and the shortest paths
#Try:
#DijP([3,{{1,2},{1,3}},table([{2, 3} = 5, {1, 3} = 1, {1, 2} = 3]));
DijP:=proc(G,a) local n,E,DT,i,N,e,T,UnVis,Vis,v,cha,rec,Nei,Tt,cu,i1,Paths,TempPaths:
n:=G[1]:
E:=G[2]:
DT:=G[3]:

for i from 1 to n do
 N[i]:={}:
od:

for e in E do
N[e[1]]:=N[e[1]] union {e[2]}:
N[e[2]]:=N[e[2]] union {e[1]}:
od:

UnVis:={seq(i,i=1..n)}:

for i from 1 to n do
Tt[i]:=infinity:
od:
Vis:=[a]:
UnVis:=UnVis minus {a}:

T[a]:=0:
Paths[a]:=[a]:
while UnVis<>{} do
cu:=Vis[-1]:
Nei:=N[cu]:

for v in Nei do
if T[cu]+DT[{cu,v}]< Tt[v] then
Tt[v]:= T[cu]+DT[{cu,v}]:
TempPaths[v]:=[op(Paths[cu]),v]:
fi:
od:

cha:=UnVis[1]:
rec:=Tt[cha]:

for i1 from 2 to nops(UnVis) do
 if Tt[UnVis[i1]]<rec then
   cha:=UnVis[i1]:
   rec:=Tt[cha]:
 fi:
od:
Vis:=[op(Vis),cha]:
T[cha]:=rec:
Paths[cha]:=TempPaths[cha]:
UnVis:=UnVis minus {cha}:
od:
  
[[seq(T[i],i=1..n)],[seq(Paths[i],i=1..n)]]


end: