Кратчайший путь в JavaScript
Я неделями искал способ вычисления кратчайших путей в JavaScript. Я играл с книгойСтруктуры данных и алгоритмы Гронер (метко названный) вhttps://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09.
Проблема, которую я продолжаю находить, состоит в том, что код так настроен, что практически невозможно переписать, чтобы получить желаемые результаты. Я хотел бы иметь возможность получить кратчайший путь из любой заданной вершины в любую другую, а не, как это кодирует Гронер, просто список всего из А. Я хотел бы иметь возможность получить, например, путь из От 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);
}