Anonymous user
Talk:Dijkstra's algorithm: Difference between revisions
→Javascript version: new section
(→Javascript version: new section) |
|||
Line 55:
Must specify explicitly that the python snippet solution should be at least in python 2.7 due to the dictionary comprehension feature used. And also, must replace the 'pushleft' with 'appendleft'.
== Javascript version ==
function navigate(numberOfIntersections, roads, start, finish) {
var vert = [],Q;
var neighb = {}, dist = {},prev = {};
for(var edge of roads){
vert.indexOf(edge.from) === -1 && vert.push(edge.from);
vert.indexOf(edge.to) === -1 && vert.push(edge.to);
if(!neighb[edge.from]) neighb[edge.from] = [];
neighb[edge.from].push({end : edge.to,cost : edge.drivingTime});
}
vert.forEach((val) => {dist[val] = Infinity;prev[val] = null});
dist[start] = 0;
Q = vert;
while(Q.length > 0){
var min = Infinity;
var u;
Q.forEach((val) => {
if(dist[val] < min){
min = dist[val];
u = val;
}
});
Q = Q.slice(0,Q.indexOf(u)).concat(Q.slice(Q.indexOf(u) + 1,Q.length));
if(dist[u] == Infinity || u == finish) break;
if(neighb[u]){
neighb[u].forEach((val) => {
var alt = dist[u] + val.cost;
if(alt < dist[val.end]){
dist[val.end] = alt;
prev[val.end] = u;
}
});
}
}
var path = [];
u = finish;
while(prev[u] !== undefined){
path.unshift(u);
u = prev[u];
}
return path.length > 0 ? path : null;
}
| |||