JavaScript中的最短路径 [英] Shortest path in JavaScript
问题描述
我一直在寻找一种计算JavaScript中最短路径的方法。我一直在使用Groner（适当命名）数据结构和算法这本书。 chapter09rel =noreferrer> https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09 。
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 Algorithms by Groner (aptly named) at https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09.
我一直在寻找的问题是代码是如此定制的，几乎不可能重写以产生所需的结果。我希望能够获得从任何给定顶点到任何其他顶点的最短路径，而不是像Groner编码那样，只是来自A的所有内容的列表。我希望能够获得，例如，路径来自F到B，或从C到A.
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.
完整的代码在这里： 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);
}
推荐答案
让我们先来说明一下广度优先搜索（BFS）如果图表未加权，则计算来自给定源顶点的最短路径。换句话说，我们将路径的长度视为路径中的边数。
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.
这是构造未加权图的简单方法：
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;
}
请注意，我们已经实现了无向图。如内联注释中所述，您可以通过从 addEdge 函数中删除四行来修改代码以构建有向图。
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 addEdge function.
BFS的这种实现在有向图上同样有效：
This implementation of BFS would 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 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);
}
以下代码段演示了您在问题中提供的图表上的这些操作。首先，我们找到可从 A 到达的所有顶点的最短路径。然后我们找到从 B 到 G 的最短路径以及 G 到 A 。
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 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(' → '));
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>
这篇关于JavaScript中的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
