Finding shortest path unweighted graph using BFS (javascript)

Question

I'm trying to apply BFS to find the length of the shortest path in a graph, but am not quite getting the right result.

I try to find the shortest path by visiting each node in the graph; then mark the ones that are visited, and continue recording the length of the path. What I hope to return is an array that contains the shortest path, but I think I am doing something wrong in the process.

I think this has something to do with how I am indexing my arrays and recording my distances.

My input is currently formatted in the form of an array that contains the neighbors for each vertex i. So, for instance, graph[i] would give you an array of neighbors of vertex i.

Any thoughts on how I can go about fixing my issue would be very helpful. Thanks!

var shortestPathLength = function(graph) {
    let distances = []
    let pq = []
    distances[0] = 0 
    let mygraph = {}

    for (var i = 0; i<graph.length; i++) {
        distances[i] = -1
        mygraph[i] = graph[i]
    }


    pq.push(mygraph[0])

    while(pq.length > 0) {
        let min_node = pq.shift()
        for(var i = 0; i<min_node.length; i++) {
            candidate = distances[i] + 1
            if(distances[min_node[i]]== -1) {
                distances[min_node[i]] = distances[i] + 1
                 pq.push(graph[min_node[i]])
            }
            else if (candidate < distances[min_node[i]]) {
                distances[min_node[i]] = distances[i] + 1
            }

        }
    }

    function getSum(total, num) {
        return total + num;
    }

    console.log(distances)
    return distances.length

};

I think distances[i] = -1 should be distances[i] = Infinity since other nodes have not been discovered yet. — kiner_shah
Are you trying to implement the Dijkstra algorithm or a BFS? — Bergi
OK. It seemed weird to me that you're calling the list pq (priority-queue?) and fetch min_nodes from it (instead of simply the first). Also for a BFS you won't need the else if branch - you will only find nodes that you didn't visit or to which you already found the minimum distance. All your edges have length 1, and a BFS will visit nodes in ascending distance order only. — Bergi

Bergi Bergi · Accepted Answer · 2018-10-20T21:55:26

Your problem is candidate = distances[i] + 1. The i is the index of the edge inside the min_node, which isn't interesting at all. What you are looking for is the current distance to the min_node. You will need to either assign the distance as a property of the min_node object itself, or you will need to store the id (index in graph) of the nodes in your queue instead of the object itself.

I've made a few other simplifications, but the only showstopper problem in your code was the distance lookup.

function shortestPathLength = function(graph) {
    const distances = Array(graph.length).fill(-1);
    distances[0] = 0; // start node
    const queue = [0];

    while (queue.length > 0) {
        const node_index = queue.shift();
//                 ^^^^^
        const edges = graph[node_index]; // get the node itself
        const candidate = distances[node_index] + 1; // outside of the loop
//      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        for (const target in edges) {
            if (distances[target] == -1) {
                distances[target] = candidate;
                queue.push(target); // not graph[target]
//                         ^^^^^^
            }
        }
    }
    return distances;
}

Finding shortest path unweighted graph using BFS (javascript)

1 Answers