Kurzester Pfad in JavaScript
Ich habe wochenlang nach einer Möglichkeit gesucht, kürzeste Wege in JavaScript zu berechnen. Ich habe mit dem Buch @ gespieDatenstrukturen und Algorithmen von Groner (treffend genannt) beihttps: //github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter0.
Das Problem ist, dass der Code so angepasst ist, dass es fast unmöglich ist, ihn neu zu schreiben, um die gewünschten Ergebnisse zu erzielen. Ich möchte in der Lage sein, den kürzesten Pfad von einem beliebigen Scheitelpunkt zu einem beliebigen anderen zu erhalten, anstatt, wie Groner es codiert, nur die Liste von allem von A. Ich möchte in der Lage sein, zum Beispiel den Pfad von zu erhalten F nach B oder von C nach A.
Der vollständige Code ist hier:http: //jsfiddle.net/8cn7e2x8
Kann jemand helfen
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);
}