JavaScript中的最短路径

Question

JavaScript中的最短路径

javascriptshortest-pathbreadth-first-search

17

我已经搜索了几周，想找到一种用JavaScript计算最短路径的方法。我一直在尝试使用Groner（非常恰当地命名）的书《数据结构与算法》中的代码，在https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09上。

我一直发现的问题是，代码非常定制化，几乎不可能重写以生成所需的结果。我希望能够从任何给定的顶点到任何其他顶点获得最短路径，而不仅仅是像Groner编码的那样从A开始的所有内容列表。例如，我想要获取从F到B的路径，或者从C到A的路径。

完整的代码在这里：http://jsfiddle.net/8cn7e2x8/

有人可以帮忙吗？

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);
}

- Tyler330

2个回答

3

阅读您的问题，我可以有两种方式阅读它...... 要么你试图减少它检查的东西，要么你试图允许自己传递变量来改变终点。我将假设前者，让其他人处理后者。

粗略地看一下问题，似乎你遇到了计算机科学中所谓的“旅行推销员问题”。这是计算机编程中的一个经典问题，被认为是一种逻辑上的不可能性，并且是“完美成为好的敌人”的一个很好的例子。

经典的旅行推销员问题是这样的，“编写一种程序，使推销员在最短时间内到达地图上的所有目的地城市。这样做而不必检查每条可能的路径。”事实上，没有（尚未）发现这样做的逻辑方法（它是否不可能或可能尚未被证明）。也就是说，如果不必是THE最短路线，而只是较短的路径，有许多捷径可以采取。一个例子是只计算从起点到终点的直线，然后将偏差推入以最接近的顶点匹配。另一个方法是将路径分解成三角形，仅将每个顶点连接到下面最接近的两个顶点，然后将它们连接在一起，直到所有顶点都连接在一起，然后仅从这些子集中计算您的起始潜在路径。

这两个答案都不能保证给出最好的答案，但它们将提供一个很好的答案，并且需要更少的计算时间，因此您不必计算从A，B和C等等来的每条路径。

- lilHar

根据第一段，我正在尝试找到从一个点到另一个点的直接路径。我已经研究了大约三个星期的A*和最短路径文章，但我没有找到任何一个能够给出好的javascript答案来找到从A到F的路径步骤，例如"A"，"B"，"E"，"F"。很惊奇有多少人都在处理这个主题，但最终并没有得到有用的结果。我已经阅读了很多伪代码，但仍在努力学习足够的知识将代码翻译成javascript。 - Tyler330

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael Laszlo · Accepted Answer

首先要指出的是，广度优先搜索(BFS)在图形无权重的情况下计算从给定源顶点到达其他顶点的最短路径。换句话说，我们将路径的长度定义为路径中边的数量。

以下是构建无权重图的简单方法：

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函数中删除四行代码来修改代码以构建定向图。

这个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 });
      }
    });
  }
}

为了找到两个给定顶点之间的最短路径并显示路径中的顶点，我们在探索图的过程中必须记住每个顶点的前身：

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);
}

以下代码片段演示了对你在问题中提供的图执行这些操作。首先，我们找到从A可达的所有顶点的最短路径。然后，我们找到从B到G和从G到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>