User Tools

Site Tools


This is an old revision of the document!


λ Dijkstras

======= Algorithm ======= <syntax js> function dijkstra(graph, source) { var openSet = new PriorityQueue(); source.distance = 0; openSet.enqueue(source); while (openSet.length > 0) { var u = openSet.dequeue(); for (var i=0, c=u.edges.count; i<c; i++) { var newDistance = u.distance + u.edges[i].distance; var target = u.edges.target; if (newDistance < target.distance) { target.distance = newDistance; openSet.sort(); } } } 4 5 for each vertex v in Graph: // Initialization 6 dist[v] ← INFINITY // Unknown distance from source to v 7 prev[v] ← UNDEFINED // Previous node in optimal path from source 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 10 dist[source] ← 0 // Distance from source to source 11 12 while Q is not empty: 13 u ← vertex in Q with min dist[u] // Source node will be selected first 14 remove u from Q 15 16 for each neighbor v of u: // where v is still in Q. 17 alt ← dist[u] + length(u, v) 18 if alt < dist[v]: // A shorter path to v has been found 19 dist[v] ← alt 20 prev[v] ← u 21 22 return dist[], prev[] </syntax> ======= Support ======= <syntax js> /* Support code... function run(args) { } */ </syntax> ======= Tests ======= <syntax js> /* Unit tests… function testA() { if (!ok) { throw "Not ok." } } */ </syntax> ======= Options ======= <syntax js> { "title":"Dijkstras", "height":"250px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script> /* Optional functions function globals() { return {}; } function args() { return null; } */ function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } var out = x.lookupInScope("out"); document.body.innerHTML = "out = "+JSON.stringify(out); } </script> </head> <body> </body> </html> </syntax>

algorithm/dijkstras.1464070973.txt.gz · Last modified: 2016/05/23 23:22 by will