20 lines
384 B
Plaintext
20 lines
384 B
Plaintext
shortestPath(G, startAt=1)={
|
|
my(n=#G[,1],dist=vector(n,i,9e99),prev=dist,Q=2^n-1);
|
|
dist[startAt]=0;
|
|
while(Q,
|
|
my(t=vecmin(vecextract(dist,Q)),u);
|
|
if(t==9e99, break);
|
|
for(i=1,#v,if(dist[i]==t && bittest(Q,i-1), u=i; break));
|
|
Q-=1<<(u-1);
|
|
for(i=1,n,
|
|
if(!G[u,i],next);
|
|
my(alt=dist[u]+G[u,i]);
|
|
if (alt < dist[i],
|
|
dist[i]=alt;
|
|
prev[i]=u;
|
|
)
|
|
)
|
|
);
|
|
dist
|
|
};
|