var findShortestPath = (graph, startNode, endNode) => {
var distances = new Map();
var parents = new Map();
distances.set(endNode, Infinity)
parents.set(endNode, null)
for (var child of graph[startNode].keys()) {
distances.set(child, graph[startNode].get(child))
//console.log(child)
//console.log(child)
parents.set(child, startNode);
}
// collect visited nodes
var visited = {};
visited[startNode] = true;
// find the nearest node
var node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
var distance = distances.get(node);
var children = graph[node];
// for each of those child nodes:
for (var child of children.entries()) {
// save the distance from the start node to the child node
var newdistance = distance + child[1];
// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
// save the distance to the object
distances.set(child[0], newdistance);
// record the path
parents.set(child[0],node);
}
}
// move the current node to the visited set
visited[node] = true;
// move to the nearest neighbor node
node = shortestDistanceNode(distances, visited);
}
// using the stored paths from start node to end node
// record the shortest path
var shortestPath = [endNode];
var parent = parents.get(endNode);
while (parent) {
shortestPath.push(parent);
parent = parents.get(parent);
}
shortestPath.reverse();
//this is the shortest path
var results = {
distance: distances.get(endNode),
path: shortestPath,
//all_distances: distances
};
// return the shortest path & the end node's distance from the start node
return results;
};var shortestDistanceNode = (distances, visited) => {
// create a default value for shortest
var shortest = null;
// for each node in the distances object
for (var node of distances.keys()) {
// if no node has been assigned to shortest yet
// or if the current node's distance is smaller than the current shortest
var currentIsShortest = shortest == null || distances.get(node) < distances.get(shortest);
// and if the current node is in the unvisited set
if (currentIsShortest && visited[node] != true) {
//visited[node] == false
// update shortest to be the current node
shortest = node;
}
}
return shortest;
};
var get_distances_from = function(graph, startNode) {
var distances = new Map();
var parents = new Map();
for (var child of graph[startNode].keys()) {
distances.set(child, graph[startNode].get(child))
//console.log(child)
//console.log(child)
parents.set(child, startNode);
}
// collect visited nodes
var visited = {};
visited[startNode] = true;
// find the nearest node
var node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
var distance = distances.get(node);
var children = graph[node];
// for each of those child nodes:
for (var child of children.entries()) {
// save the distance from the start node to the child node
var newdistance = distance + child[1];
// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
// save the distance to the object
distances.set(child[0], newdistance);
// record the path
parents.set(child[0],node);
}
}
// move the current node to the visited set
visited[node] = true;
// move to the nearest neighbor node
node = shortestDistanceNode(distances, visited);
}
return distances;
};graph
var right_graph = new Graph();
var startPoint;
for (var i in edges) {
var p1 = new GraphVertex(edges[i][0].name);
var p2 = new GraphVertex(edges[i][1].name);
if (edges[i][0].name == this.id) {
startPoint = p1
}
if (edges[i][1].name == this.id) {
startPoint = p2
}
var weight = edges[i][3]
var edge = new GraphEdge(p1, p2, weight)
right_graph.addEdge(edge)
}
var res = dijkstra(right_graph, startPoint);edges:
visited var shortestDistanceNode = (distances, visited) => {
// create a default value for shortest
var shortest = null;
// for each node in the distances object
for (var node in distances) {
// if no node has been assigned to shortest yet
// or if the current node's distance is smaller than the current shortest
var currentIsShortest =
shortest === null || distances[node] < distances[shortest];
// and if the current node is in the unvisited set
if (currentIsShortest && visited[node] != true) {
//visited[node] == false
// update shortest to be the current node
shortest = node;
}
}
return shortest;
};
var findShortestPath = (graph, startNode, endNode) => {
// track distances from the start node using a hash object
var distances = {};
distances[endNode] = "Infinity";
distances = Object.assign(distances, graph[startNode]);
// track paths using a hash object
var parents = { endNode: null };
for (var child in graph[startNode]) {
parents[child] = startNode;
}
// collect visited nodes
var visited = {};
// find the nearest node
var node = shortestDistanceNode(distances, visited);
// for that node:
while (node) {
// find its distance from the start node & its child nodes
var distance = distances[node];
var children = graph[node];
// for each of those child nodes:
for (var child in children) {
// make sure each child node is not the start node
if (child === startNode) {
continue;
} else {
// save the distance from the start node to the child node
var newdistance = distance + children[child];
// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
if (!distances[child] || distances[child] > newdistance) {
// save the distance to the object
distances[child] = newdistance;
// record the path
parents[child] = node;
}
}
}
// move the current node to the visited set
visited[node] = true;
// move to the nearest neighbor node
node = shortestDistanceNode(distances, visited);
}
// using the stored paths from start node to end node
// record the shortest path
var shortestPath = [endNode];
var parent = parents[endNode];
while (parent) {
shortestPath.push(parent);
parent = parents[parent];
}
shortestPath.reverse();
//this is the shortest path
var results = {
distance: distances[endNode],
path: shortestPath,
all_distances: distances
};
// return the shortest path & the end node's distance from the start node
return results;
};var s_time = performance.now()
var max_i = 160*160*60*10
var x;
for (var i=0; i < max_i; i++) {
x = Math.random()
}
console.log(performance.now()-s_time)