Shortest path choices

Questions 1 to 5 of 8

1. 1. You need the distance from one source to every vertex. There are up to 200000 vertices and 200000 edges, and each weight is an integer from 0 to 10^9. Which method fits?

   Floyd-Warshall, because it finds every distance0-1 BFS, because it runs in linear timeDijkstra with a binary heap, because all weights are 0 or moreDijkstra with every weight changed to 1, so that BFS applies
2. 2. Your graph has only weights 0 and 1, one source and 200000 vertices. An AI tool wrote the solution with Dijkstra and a heap. What is the best answer?

   Use 0-1 BFS with a deque: O(n + m). Dijkstra's answers are also right here, but it costs O((n + m) log m).Dijkstra gives wrong distances whenever a weight is 0, so the code must be rewritten.Use Floyd-Warshall, because a 0 weight needs all pairs of vertices.Dijkstra is correct only when every weight is 1, so use a plain queue for every edge.
3. 3. How many inner-loop steps does Floyd-Warshall take on a graph with n = 400 vertices? Count one step for each triple (k, i, j), with k, i and j each running from 0 to n - 1.

   Type a number.

4. 4. Which statements about lazy deletion in Dijkstra are true? Choose all that apply.

   Pick every answer that is true.

   A heap cannot lower the key of an item already inside it, so a better distance is pushed as a new pair.When a popped distance is larger than the current dist[u], that pair is stale and is skipped.Each successful relaxation adds at most one heap entry, so the heap holds at most m + 1 entries in total.The old entry is removed from the heap at the moment its distance improves.
5. 5. An AI tool writes Dijkstra for a road map where one edge has weight -3, and says the answers are correct. Which reply is right?

   Dijkstra's answers are correct, because a negative edge only makes the heap slower.Replace -3 with 0. The distances will be right and nothing else changes.Dijkstra is fine if the heap is a max-heap, because negative values then come out first.Dijkstra can give wrong distances, because a popped value may not be final. For one source with negative weights, use Bellman-Ford, which runs in O(n m).