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]
43

DFS Solution

from typing import List

def get_neighbors(graph, node):
    return graph[node]

def shortest_path(graph: List[List[int]], a: int, b: int) -> int:
    visited = set()
    min_distance = float('inf')

    def dfs(node, depth):
        nonlocal min_distance, visited
        if node == b:
            min_distance = min(min_distance, depth)
            return

        visited.add(node)

        for neighbor in get_neighbors(graph, node):
            if neighbor not in visited:
                dfs(neighbor, depth + 1)

        visited.remove(node)

    dfs(a, 0)
    return min_distance if min_distance != float('inf') else -1
44

In Javascript the time complexity for Array.shift() is O(n) in the worst case. Wouldn’t it impact the overall time complexity for the solution, since it is inside the loop?

45

you mistake was local reinitializing queue, instead of updating the global queue
queue := queue[1:]

change it to
queue = queue[1:]