Estou procurando há semanas uma maneira de calcular os caminhos mais curtos em JavaScript. Eu tenho brincado com o livroEstruturas de dados e algoritmos por Groner (apropriadamente chamado) emhttps://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09.

O problema que continuo encontrando é que o código é tão personalizado que é quase impossível reescrever para produzir os resultados desejados. Gostaria de conseguir o caminho mais curto de um vértice para outro, em vez de, como Groner o codifica, apenas a lista de tudo de A. Gostaria de conseguir, por exemplo, o caminho de F a B ou de C a A.

O código completo está aqui:http://jsfiddle.net/8cn7e2x8/

Alguém pode ajudar?

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