JavaScript 中的最短路径
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32527026/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Shortest path in JavaScript
提问by Tyler330
I have been searching for weeks for a way to compute shortest paths in JavaScript. I have been playing with the book Data Structures and Algorithmsby Groner (aptly named) at https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09.
我一直在寻找一种在 JavaScript 中计算最短路径的方法。我在https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09 上玩了 Groner的《数据结构和算法》一书（恰如其分地命名） 。
The trouble I keep on finding is that the code is so customized that it is almost impossible to rewrite to produce the desired results. I would like to be able to get the shortest path from any given vertex to any other, rather than, as Groner codes it, just the list of everything from A. I would like to be able to get, for example, the path from F to B, or from C to A.
我不断发现的问题是代码是如此定制，以至于几乎不可能重写以产生所需的结果。我希望能够获得从任何给定顶点到任何其他顶点的最短路径，而不是像 Groner 编码的那样，只是从 A 中获取所有内容的列表。例如，我希望能够获得从F 到 B，或从 C 到 A。
The full code is here: http://jsfiddle.net/8cn7e2x8/
完整代码在这里：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);
}
回答by Michael Laszlo
Let us begin by remarking that breadth-first search (BFS) computes the shortest paths from a given source vertex if the graph is unweighted. In other words, we consider the length of a path to be the number of edges in the path.
让我们首先说明，如果图未加权，广度优先搜索 (BFS) 会计算来自给定源顶点的最短路径。换句话说，我们将路径的长度视为路径中的边数。
Here is an easy way to construct 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;
}
Note that we have implemented an undirected graph. As mentioned in the inline comments, you can modify the code to construct a directed graph by deleting four lines from the addEdgefunction.
请注意，我们已经实现了一个无向图。如内联注释中所述，您可以通过从addEdge函数中删除四行来修改代码以构建有向图。
This implementation of BFS would work equally well on a directed graph:
BFS 的这种实现在有向图上同样有效：
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 have to remember the predecessor of each vertex as we explore 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) {
path.push(u);
u = predecessor[u];
}
path.push(u);
path.reverse();
print(path.join(' → '));
return;
}
predecessor[v] = u;
queue.push(v);
}
}
print('there is no path from ' + source + ' to ' + target);
}
The following snippet demonstrates these operations on the graph that you gave in your question. First we find the shortest paths to all vertices reachable from A. Then we find the shortest path from Bto Gand from Gto A.
以下代码段演示了您在问题中给出的图表上的这些操作。首先，我们找到从 可到达的所有顶点的最短路径A。然后我们找到从BtoG和 from Gto的最短路径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(' → '));
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>回答by liljoshu
Reading your question, I can read it one of two ways... Either you're trying to reduce the amount of things it checks, or you're trying to allow yourself to pass in variables to change end points. I'm going to assume the former and let someone else handle the latter case.
阅读您的问题，我可以通过以下两种方式阅读它...要么您试图减少它检查的内容数量，要么您试图让自己传入变量以更改端点。我将假设前者并让其他人处理后一种情况。
Giving a cursory glance over the problem, it looks like you've come across what is known in Comp Sci as "The traveling salesman problem." It's a classical problem in computer programming that's considered a logical impossibility, and is a good example of "perfect being the enemy of the good."
粗略地看一下这个问题，您似乎遇到了 Comp Sci 中称为“旅行商问题”的问题。这是计算机编程中的一个经典问题，被认为是逻辑上的不可能，并且是“完美与善的敌人”的一个很好的例子。
The classical travelling salesman problem is this, "Program a way for a salesman to reach all of his destination cities on a map in the shortest time. Do so without having to check every single possible path." The thing is, logical way to do this has (yet) to ever be discovered (it's yet to be proved if it's impossible or possible). That said, if it doesn't have to be THE shortest, but just a shorter path, there's a number of shortcuts that can be taken. One example is just calculating a line from start to finish, and then push in the deviations to match up with closest vertices. Another is to break the paths into triangles that connect each vertices only to the next closest two vertices and then connect clumps the same way until all vertices are connected and then only calculate your starting potential paths from those subsets.
经典的旅行推销员问题是这样的，“为推销员设计一种在最短的时间内到达地图上所有目的地城市的方法。这样做而不必检查每条可能的路径。” 问题是，做到这一点的合乎逻辑的方法（尚未）被发现（如果不可能或可能，还有待证明）。也就是说，如果它不必是最短的，而只是更短的路径，那么可以采取许多捷径。一个例子是从头到尾计算一条线，然后推入偏差以匹配最近的顶点。
Neither of those two answers are guaranteed to give you the best answer, but they will provide a good answer with a lot less computational time required so you don't have to calculate every path coming from A and B and C etc. etc.
这两个答案都不能保证给你最好的答案，但它们会提供一个很好的答案，所需的计算时间要少得多，所以你不必计算来自 A、B 和 C 等的每条路径。
