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();
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;
}
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[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
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], [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]
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
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?