The shortest way in JavaScript

Question

I searched for weeks for a way to calculate shortest paths in JavaScript. I played with the Groner Data Structures and Algorithms book (exactly named) at https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09 .

The problem that I continue to find is that the code is set up so that it is practically impossible to rewrite it to get the desired results. I would like to be able to get the shortest path from any given vertex to any other, and not, as Groner does, just a list of everything from A. I would like to get, for example, the path from F to B, or from C to A.

The full code is here: http://jsfiddle.net/8cn7e2x8/

Can anyone help?

var graph = new Graph(); var myVertices = ['A','B','C','D','E','F']; for (var i=0; i<myVertices.length; i++) { graph.addVertex(myVertices[i]); } graph.addEdge('A', 'B'); graph.addEdge('B', 'C'); graph.addEdge('B', 'E'); graph.addEdge('C', 'D'); graph.addEdge('C', 'E'); graph.addEdge('C', 'G'); graph.addEdge('D', 'E'); graph.addEdge('E', 'F'); graph.dfs(); console.log('********* sortest path - BFS ***********'); var shortestPathA = graph.BFS(myVertices[0]); //from A to all other vertices var fromVertex = myVertices[0]; for (i = 1; i < myVertices.length; i++) { var toVertex = myVertices[i], path = new Stack(); for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) { path.push(v); } path.push(fromVertex); var s = path.pop(); while (!path.isEmpty()) { s += ' - ' + path.pop(); } console.log(s); } 

Answer 1

Let's start with the observation that BFS searches for shortest paths from a given vertex in a source if the graph is unweighted. In other words, we consider the path length as the number of edges in the path.

Here is a simple way to build an unweighted graph:

 function Graph() { var neighbors = this.neighbors = {}; // Key = vertex, value = array of neighbors. this.addEdge = function (u, v) { if (neighbors[u] === undefined) { // Add the edge u -> v. neighbors[u] = []; } neighbors[u].push(v); if (neighbors[v] === undefined) { // Also add the edge v -> u so as neighbors[v] = []; // to implement an undirected graph. } // For a directed graph, delete neighbors[v].push(u); // these four lines. }; return this; } 

Please note that we have implemented an undirected graph. As indicated in the inline comments, you can change the code to build a directed graph by removing four lines from the addEdge function.

This BFS implementation will work equally well on a directed graph:

 function bfs(graph, source) { var queue = [ { vertex: source, count: 0 } ], visited = { source: true }, tail = 0; while (tail < queue.length) { var u = queue[tail].vertex, count = queue[tail++].count; // Pop a vertex off the queue. print('distance from ' + source + ' to ' + u + ': ' + count); graph.neighbors[u].forEach(function (v) { if (!visited[v]) { visited[v] = true; queue.push({ vertex: v, count: count + 1 }); } }); } } 

To find the shortest path between two given vertices and display the vertices along the path, we must remember the predecessor of each vertex when we examine the graph:

 function shortestPath(graph, source, target) { if (source == target) { // Delete these four lines if print(source); // you want to look for a cycle return; // when the source is equal to } // the target. var queue = [ source ], visited = { source: true }, predecessor = {}, tail = 0; while (tail < queue.length) { var u = queue[tail++], // Pop a vertex off the queue. neighbors = graph.neighbors[u]; for (var i = 0; i < neighbors.length; ++i) { var v = neighbors[i]; if (visited[v]) { continue; } visited[v] = true; if (v === target) { // Check if the path is complete. var path = [ v ]; // If so, backtrack through the path. while (u !== source) { u = predecessor[u]; path.push(u); } path.reverse(); print(path.join(' &rarr; ')); return; } predecessor[v] = u; queue.push(v); } } print('there is no path from ' + source + ' to ' + target); } 

The following snippet demonstrates these operations on the chart that you indicated in your question. First we find the shortest paths to all the vertices reachable from A Then we find the shortest path from B to G and from G to A

 function Graph() { var neighbors = this.neighbors = {}; // Key = vertex, value = array of neighbors. this.addEdge = function (u, v) { if (neighbors[u] === undefined) { // Add the edge u -> v. neighbors[u] = []; } neighbors[u].push(v); if (neighbors[v] === undefined) { // Also add the edge v -> u in order neighbors[v] = []; // to implement an undirected graph. } // For a directed graph, delete neighbors[v].push(u); // these four lines. }; return this; } function bfs(graph, source) { var queue = [ { vertex: source, count: 0 } ], visited = { source: true }, tail = 0; while (tail < queue.length) { var u = queue[tail].vertex, count = queue[tail++].count; // Pop a vertex off the queue. print('distance from ' + source + ' to ' + u + ': ' + count); graph.neighbors[u].forEach(function (v) { if (!visited[v]) { visited[v] = true; queue.push({ vertex: v, count: count + 1 }); } }); } } function shortestPath(graph, source, target) { if (source == target) { // Delete these four lines if print(source); // you want to look for a cycle return; // when the source is equal to } // the target. var queue = [ source ], visited = { source: true }, predecessor = {}, tail = 0; while (tail < queue.length) { var u = queue[tail++], // Pop a vertex off the queue. neighbors = graph.neighbors[u]; for (var i = 0; i < neighbors.length; ++i) { var v = neighbors[i]; if (visited[v]) { continue; } visited[v] = true; if (v === target) { // Check if the path is complete. var path = [ v ]; // If so, backtrack through the path. while (u !== source) { path.push(u); u = predecessor[u]; } path.push(u); path.reverse(); print(path.join(' &rarr; ')); return; } predecessor[v] = u; queue.push(v); } } print('there is no path from ' + source + ' to ' + target); } function print(s) { // A quick and dirty way to display output. s = s || ''; document.getElementById('display').innerHTML += s + '<br>'; } window.onload = function () { var graph = new Graph(); graph.addEdge('A', 'B'); graph.addEdge('B', 'C'); graph.addEdge('B', 'E'); graph.addEdge('C', 'D'); graph.addEdge('C', 'E'); graph.addEdge('C', 'G'); graph.addEdge('D', 'E'); graph.addEdge('E', 'F'); bfs(graph, 'A'); print(); shortestPath(graph, 'B', 'G'); print(); shortestPath(graph, 'G', 'A'); }; 

 body { font-family: 'Source Code Pro', monospace; font-size: 12px; } 

 <link rel="stylesheet" type="text/css" href="https://fonts.googleapis.com/css?family=Source+Code+Pro"> <div id="display"></id> 

Answer 2

While reading my question, I can read it in one of two ways ... Either you are trying to reduce the number of things that it checks, or you are trying to allow yourself to pass variables to change endpoints. I am going to take the first and let someone else handle the last case.

A quick look at the problem, it seems that you are faced with what is known in Comp Sci as the "Salesman Problem". This is a classic problem in computer programming, which considered logical impossibility, and is a good example of "ideal to be the enemy of good."

The classic traveling salesman problem is this: "Program the way so that the seller can get to all destination cities on the map as soon as possible. Don't do this without checking every possible way." The fact is that a logical way to do this (for now) be detected (not yet proven if this is not possible or possible). However, if it should not be the shortest, but only the shorter way, there are a number of shortcuts that you can use. One example is simply calculating a line from start to finish, and then pushing into the deviations to match the nearest vertices. Another is the partitioning of paths into triangles that connect each vertex only with the nearest two vertices, and then connect the clumps in the same way until all the vertices are connected, and then only calculate the starting potential paths from these subsets.

None of these two answers will give you a better answer, but they will provide a good answer with much less computational time, so you do not need to calculate every path coming from A and B and C, etc. and etc.