Practice Space Complexity Considerations (1.8) - All-pairs Shortest Paths

Practice: Space Complexity Considerations

Lesson 1.8All-pairs Shortest Paths

Practise this section

9 questions

Flashcard drill
3 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What does the Floyd-Warshall algorithm compute?
Show hintHide hint
Think about what you want to find in the graph.
Question 2.
Does the Floyd-Warshall algorithm work with negative edge weights?
Show hintHide hint
Consider what negative cycles do to path calculations.
3Question 3.
What is the time complexity of the Floyd-Warshall algorithm?
- O(n)
- O(n²)
- O(n³)
Show hintHide hint
Think about how many vertices are involved in the updates.
4Question 4.
True or False: The Floyd-Warshall algorithm can handle graphs with negative cycles.
- True
- False
Show hintHide hint
Remember that negative cycles alter path finding.
Question 5.
Consider a directed graph with vertices A, B, C, and D. The edges are as follows: A to B (3), A to C (5), B to D (2), and C to D (1). Compute the shortest paths between all pairs using the Floyd-Warshall method.
Show hintHide hint
Use the initial weight matrix to track distances through each step.
Question 6.
Design an example graph that contains a negative cycle. Explain why the Floyd-Warshall algorithm cannot provide a valid solution for this graph.
Show hintHide hint
Focus on how negative edge weights contribute to cycles when combined.

5 more questions in this section. Enroll free to practise them all.