# Shortest Path - Graph / Vanilla BFS

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

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

Input:
n
1 node
2 nodes

n
a
b

Welp… looks like this site doesnt support formatting that well

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

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

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.

Structured Programming JS Solution:

``````function shortestPath(graph, root, target) {
const queue = [root];
const visited = new Set();

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

return level;
}
``````

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

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

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
}
``````

tests:

``````def test_shortestpath():
inputs = [
[[[1, 2], [0, 2, 3], [0, 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], , ], 1, 2],
[[, ], 1, 0],
]
expected = [2, 5, 2, 1]
``````