Dijkstra's algorithm: Difference between revisions

</pre>

=={{header|zkl}}==

<lang zkl>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; }

}

}

}</lang>

<lang zkl>graph:=Dictionary( // directed graph

"a", T(T("b", 7.0), T("c", 9.0), T("f",14.0)),

"b", T(T("c",10.0), T("d",15.0)),

"c", T(T("d",11.0), T("f", 2.0)),

"d", T(T("e", 6.0)),

"e", T(T("f", 9.0)),

"f", T,

);

dijkstra(graph,"a","e").println();

dijkstra(graph,"e","a").println();</lang>

{{out}}

<pre>

L("a","c","d","e")

Can't get there