[Question]Is there a way to get all shortest path?

[kilik52]

Function shortestPath only returns one of the shortest path. Is there a way to get all shortest path? Thanks

[curran]

I'd welcome a PR that introduces a function to get all shortest paths, or a flag on the existing one.

[curran]

An interesting read https://www.quora.com/If-multiple-shortest-paths-exists-between-2-nodes-in-an-undirected-graph-is-it-possible-to-print-all-of-them-using-Dijkstras-algorithm

[krm35]

https://github.com/datavis-tech/graph-data-structure/pull/69

[curran]

Closed in https://github.com/datavis-tech/graph-data-structure/pull/69

[curran]

I haven't researched if that implementation is the optimal algorithm for this, but it seems to work and is a great first stab. Thanks for the PR!

[krm35]

I've tryied to implement Bellman-Ford and Floyd-Warshall but clearly on a big graph, the process takes a while (1 second).

The code is from there

https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/graph/bellman-ford/bellmanFord.js

https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/graph/floyd-warshall/floydWarshall.js

const Graph = require('graph-data-structure');

function buildGraph(graph, cells, diagonal) {
    let id = 0;
    for (let line = 1; line <= 40; line++) {
        for (let column = 1; column <= 14; column++) {
            const pair = (line - 1) % 2 === 0;
            if (cells[id]?.mov) {
                (pair ? [13, 14] : [14, 15]).forEach((value, i) => {
                    if (i && !pair && column === 14) return;
                    if (!i && pair && column === 1) return;
                    if (cells[id + value]?.mov) {
                        graph.addEdge(id, id + value, 1);
                        graph.addEdge(id + value, id, 1);
                    }
                });
                if (diagonal) {
                    [1, 28].forEach((value, i) => {
                        if (!i && column === 14) return;
                        if (cells[id + value]?.mov) {
                            graph.addEdge(id, id + value, 1);
                            graph.addEdge(id + value, id, 1);
                        }
                    });
                }
            }
            id++;
        }
    }
}

const graph = Graph();
const cells = Array(560).fill({mov: true});
let start;
buildGraph(graph, cells, true);
start = Date.now();
//console.log
(floydWarshall({
        getAllVertices: () => {
            const nodes = graph.serialize().nodes;
            nodes.forEach(node => node.getKey = () => node.id);
            return nodes;
        },
        getVertexByKey: (node) => {
            return {id: node, getKey: () => node};
        },
        getNeighbors: (node) => graph.adjacent(node.id),
        findEdge: (u, v) => {
            return {weight: graph.getEdgeWeight(u, v)}
        }
    },
    {getKey: () => 400}
));
console.log(Date.now() - start, "ms");
start = Date.now();
//console.log
(bellmanFord({
        getAllVertices: () => {
            const nodes = graph.serialize().nodes;
            nodes.forEach(node => node.getKey = () => node.id);
            return nodes; // [{ source: '17', target: 31, weight: 1 },]
        },
        getVertexByKey: (node) => {
            return {id: node, getKey: () => node};
        },
        getNeighbors: (node) => graph.adjacent(node.id),
        findEdge: (u, v) => {
            return {weight: graph.getEdgeWeight(u, v)}
        }
    },
    {getKey: () => 400}
));

console.log(Date.now() - start, "ms");

function floydWarshall(graph) {
    // Get all graph vertices.
    const vertices = graph.getAllVertices();

    // Init previous vertices matrix with nulls meaning that there are no
    // previous vertices exist that will give us shortest path.
    const nextVertices = Array(vertices.length).fill(null).map(() => {
        return Array(vertices.length).fill(null);
    });

    // Init distances matrix with Infinities meaning there are no paths
    // between vertices exist so far.
    const distances = Array(vertices.length).fill(null).map(() => {
        return Array(vertices.length).fill(Infinity);
    });

    // Init distance matrix with the distance we already now (from existing edges).
    // And also init previous vertices from the edges.
    vertices.forEach((startVertex, startIndex) => {
        vertices.forEach((endVertex, endIndex) => {
            if (startVertex === endVertex) {
                // Distance to the vertex itself is 0.
                distances[startIndex][endIndex] = 0;
            } else {
                // Find edge between the start and end vertices.
                const edge = graph.findEdge(startVertex, endVertex);

                if (edge) {
                    // There is an edge from vertex with startIndex to vertex with endIndex.
                    // Save distance and previous vertex.
                    distances[startIndex][endIndex] = edge.weight;
                    nextVertices[startIndex][endIndex] = startVertex;
                } else {
                    distances[startIndex][endIndex] = Infinity;
                }
            }
        });
    });

    // Now let's go to the core of the algorithm.
    // Let's all pair of vertices (from start to end ones) and try to check if there
    // is a shorter path exists between them via middle vertex. Middle vertex may also
    // be one of the graph vertices. As you may see now we're going to have three
    // loops over all graph vertices: for start, end and middle vertices.
    vertices.forEach((middleVertex, middleIndex) => {
        // Path starts from startVertex with startIndex.
        vertices.forEach((startVertex, startIndex) => {
            // Path ends to endVertex with endIndex.
            vertices.forEach((endVertex, endIndex) => {
                // Compare existing distance from startVertex to endVertex, with distance
                // from startVertex to endVertex but via middleVertex.
                // Save the shortest distance and previous vertex that allows
                // us to have this shortest distance.
                const distViaMiddle = distances[startIndex][middleIndex] + distances[middleIndex][endIndex];

                if (distances[startIndex][endIndex] > distViaMiddle) {
                    // We've found a shortest pass via middle vertex.
                    distances[startIndex][endIndex] = distViaMiddle;
                    nextVertices[startIndex][endIndex] = middleVertex;
                }
            });
        });
    });

    // Shortest distance from x to y: distance[x][y].
    // Next vertex after x one in path from x to y: nextVertices[x][y].
    return {distances, nextVertices};
}

function bellmanFord(graph, startVertex) {
    const distances = {};
    const previousVertices = {};

    // Init all distances with infinity assuming that currently we can't reach
    // any of the vertices except start one.
    distances[startVertex.getKey()] = 0;
    graph.getAllVertices().forEach((vertex) => {
        previousVertices[vertex.getKey()] = null;
        if (vertex.getKey() != startVertex.getKey()) {
            distances[vertex.getKey()] = Infinity;
        }
    });

    // We need (|V| - 1) iterations.
    for (let iteration = 0; iteration < (graph.getAllVertices().length - 1); iteration += 1) {
        // During each iteration go through all vertices.
        Object.keys(distances).forEach((vertexKey) => {
            const vertex = graph.getVertexByKey(vertexKey);

            // Go through all vertex edges.
            graph.getNeighbors(vertex).forEach((n) => {
                const edge = graph.findEdge(vertex, n);
                const neighbor = {getKey: () => n};
                // Find out if the distance to the neighbor is shorter in this iteration
                // then in previous one.
                const distanceToVertex = distances[vertex.getKey()];
                const distanceToNeighbor = distanceToVertex + edge.weight;
                if (distanceToNeighbor < distances[neighbor.getKey()]) {
                    distances[neighbor.getKey()] = distanceToNeighbor;
                    previousVertices[neighbor.getKey()] = vertex;
                }
            });
        });
    }

    return {
        distances,
        previousVertices,
    };
}

[curran]

Oh nice! Thank you for sharing the reference.