Shortest Path - Graph / Vanilla BFS

Problems
31

The input in test 1 is confusing. Does it mean the following which is not an undirected graph?

0:4
1:1 2
2:0 2 3
3:0 1
4:1
5:0
6:3

32

How to input custom test
n = graph.size() in my demo

Input:
n
1 node
2 nodes
…
n
a
b

33

Welp… looks like this site doesnt support formatting that well

34

who tf wrote these javascript solutions. why is there a method to just get the key value pair. Honestly makes it more confusing and more code for no reason

35 
private static List<Integer> getNeighbors(List<List<Integer>> graph, int node) {
        return graph.get(node);
    }
36

I think its cause they’re trying to follow the “template”. Either way i’m just mad theres no native heap/pqueue support for js.

37

Structured Programming JS Solution:

function shortestPath(graph, root, target) {
    const queue = [root];
    const visited = new Set();
    visited.add(root);
    
    let level = -1;
    let foundTarget = false;
    
    while (queue.length > 0 && !foundTarget) {
         level += 1;
        
         for (
             let i = 0; 
             i < queue.length && !foundTarget; 
             i++
         ) {
             const node = queue.shift();

             if (node == target) {
                 foundTarget = true;
             } else {
                 for (const neighbor of graph[node]) {
                     if (!visited.has(neighbor)) {
                         queue.push(neighbor);
                         visited.add(neighbor);
                     }
                 }
             }
         }
    }
    
    return level;
}
38

Same as other comments: more tests would be great. And adding a visual representation of the graph (in tests) could help to understand

39

hi guys, i use golang for this problem, at first i use my solution and Time limit exceeded happened.
so, i convert the solution to Golang but still have the time limit,
here’s my code.

func shortestPath(graph [][]int, a int, b int) int {
    queue := make([]int, 0)
    queue = append(queue, a)
    visited := make(map[int]bool)
    visited[a] = true
    level := 0
    for len(queue) > 0 {
        n := len(queue)
        for i:=0; i<n; i++ {
            node := queue[0]
            queue := queue[1:]   
            if node == b {
                return level
            }
            for _, neighbour := range graph[node] {
                if _, ok := visited[neighbour]; ok {
                    continue
                }
                queue = append(queue,  neighbour)
                visited[neighbour]=true
            }    
        }
        level++
    }
    return level
}

Is my code wrong? or is it a bug from algomonster? thanks

40

nevermind guys, it’s my code tehe
i took a little optimization in golang slice

func shortestPath(graph [][]int, a int, b int) int {
    queue := make([]int, 0)
    queue = append(queue, a)
    
    visited := make(map[int]bool)
    visited[a] = true
    level :=0
    for len(queue) > 0 {
        n := len(queue)
        for i:=0; i<n; i++ {
            node := queue[i]
            if node == b {
                return level
            }    
            for _, neighbour := range graph[node] {
                if _, ok := visited[neighbour]; ok {
                    continue
                }
                queue = append(queue, neighbour)
                visited[neighbour] = true
            }
            
        }
        queue = queue[n:]
        level++
    }
    return level
}
41

tests:

def test_shortestpath():
    inputs = [
        [[[1, 2], [0, 2, 3], [0, 1], [1]], 0, 3],
        [
            [
                [1, 4],
                [0, 2],
                [1, 3],
                [2, 4, 5],
                [0, 3],
                [3, 6, 9],
                [5, 8],
                [8, 9],
                [6, 7],
                [5, 7],
            ],
            0,
            7,
        ],
        [[[1, 2], [0], [0]], 1, 2],
        [[[1], [0]], 1, 0],
    ]
    expected = [2, 5, 2, 1]