BFS that times out on large grids

This shortest-path BFS on a grid is correct and runs instantly on a 100 × 100 grid, but on a 2000 × 2000 open grid it takes minutes. The reviewer says "the algorithm is O(V + E), so it must be the machine". Prove them wrong.

1function shortestPath(grid) {
2  const rows = grid.length, cols = grid[0].length;
3  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
4  const queue = [[0, 0]];
5  dist[0][0] = 0;
6 
7  while (queue.length > 0) {
8    const [r, c] = queue.shift();
9    if (r === rows - 1 && c === cols - 1) return dist[r][c];
10    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
11      const nr = r + dr, nc = c + dc;
12      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
13      if (grid[nr][nc] === 1 || dist[nr][nc] !== -1) continue;
14      dist[nr][nc] = dist[r][c] + 1;
15      queue.push([nr, nc]);
16    }
17  }
18  return -1;
19}
20 
21const big = Array.from({ length: 2000 }, () => new Array(2000).fill(0));
22console.time('bfs');
23console.log(shortestPath(big));   // 3998, but very slow
24console.timeEnd('bfs');

1. What is the cost of Array.prototype.shift() on an array of length m? Why?
2. Derive the actual complexity of this BFS as a function of the number of cells V.
3. Give two fixes that restore O(V) dequeue cost, and compare them.
4. Does the same problem affect pop(), push(), unshift(), splice(0, 1)?
5. State the complexity before and after.