23 lines
673 B
Plaintext
23 lines
673 B
Plaintext
const INF=(0).MAX;
|
|
fcn dijkstra(graph,start,dst){
|
|
Q :=graph.copy();
|
|
prev:=graph.keys.pump(Dictionary().add.fp1(Void));
|
|
dist:=graph.keys.pump(Dictionary().add.fp1(INF));
|
|
dist[start]=0;
|
|
while(Q){
|
|
Q.reduce('wrap(min,[(v,_)],ru){
|
|
if((d:=dist[v])<min){ ru.set(v); d } else min },
|
|
INF,ru:=Ref(Void));
|
|
if(not u:=ru.value) return("Can't get there");
|
|
if(u==dst){
|
|
S:=List(); do{ S.append(u); u=prev[u]; }while(u);
|
|
return(S.reverse());
|
|
}
|
|
Q.del(u);
|
|
foreach v,len in (graph[u]){ // (neighborVertex,len to neighbor)...
|
|
alt:=dist[u] + len;
|
|
if(alt<dist[v]){ dist[v]=alt; prev[v]=u; }
|
|
}
|
|
}
|
|
}
|