Help18:=proc(): print(` RWG(n,K), SD(M,a,b) `): end:

#RWG(n,K): random weighted directed graph on N vertices given as a matrix with entries from 0 to K
RWG:=proc(n,K) local i,j,ra:
ra:=rand(0..K):
[seq([seq(ra(),j=1..i-1),0,seq(ra(),j=i+1..n)],i=1..n)]:
end:

#SD(M,a,b): The total distance of the shortest path from vertex a to vertex b
SD:=proc(M,a,b) local n, i,j,Per,TempTable, PerTable,cu,x:
n:=nops(M):
Per:=[a]:

for i from 1 to n do
 TempTable[i]:=infinity:
od:

PerTable[a]:=0:
while not member(b, {op(Per)}) do
cu:=Per[-1]:

for j from 1 to n do
 if j<>cu then
 TempTable[j]:=min(TempTable[j],M[cu][j]+PerTable[cu]):
 fi:
od:

x:=min[index]([seq(TempTable[j],j=1..n)]):
Per:=[op(Per),x]:
PerTable[x]:=TempTable[x]:
TempTable[x]:=infinity:
od:


PerTable[b]:

end: