Understanding All-Pairs Shortest Path: Floyd-Warshall and Johnson’s Algorithms Quiz

Explore key concepts of All-Pairs Shortest Path algorithms, focusing on Floyd-Warshall and Johnson’s methods, including their features, use cases, and differences. This easy quiz helps solidify your grasp on algorithm steps, graph characteristics, and practical considerations for these popular graph algorithms.

1. Floyd-Warshall Main Principle

   Which fundamental strategy does the Floyd-Warshall algorithm use to find shortest paths between all pairs of vertices in a weighted graph?

   1. Divide and conquer
   2. Backtracking
   3. Dynamic programming
   4. Greedy choice

   Explanation: Floyd-Warshall algorithm applies dynamic programming by building solutions to subproblems and combining them. Greedy choice is common in algorithms like Dijkstra, not Floyd-Warshall. Divide and conquer breaks problems into independent subproblems, which Floyd-Warshall does not do. Backtracking is unrelated to shortest path computation here, making dynamic programming the correct answer.

2. Support for Negative Edge Weights

   When is it appropriate to use the Floyd-Warshall algorithm considering negative edge weights in a graph?

   1. All edge weights are zero
   2. There are negative cycles in the graph
   3. The graph only contains positive edge weights
   4. The graph has negative edge weights but no negative cycles

   Explanation: Floyd-Warshall can handle negative edge weights as long as there are no negative cycles. Using it on graphs with only positive weights is possible but not its main distinction. If negative cycles are present, Floyd-Warshall will not produce correct shortest paths. All zero edge weights are an unrelated scenario.

3. Time Complexity Identification

   What is the time complexity of the Floyd-Warshall algorithm for a graph with n vertices?

   1. O(n log n)
   2. O(n^2)
   3. O(n^3)
   4. O(2^n)

   Explanation: The time complexity of Floyd-Warshall is O(n^3) because it has three nested loops over the vertices. O(n^2) suggests a simpler algorithm, which isn't the case here. O(n log n) is typical for efficient single-source algorithms. O(2^n) is exponential and does not apply to Floyd-Warshall.

4. Johnson’s Algorithm—Negative Edges Support

   What unique feature of Johnson’s algorithm allows it to work with graphs having negative edge weights?

   1. It reweights edges to eliminate negative weights
   2. It ignores negative edge weights
   3. It splits negative-weight edges into multiple positive edges
   4. It cycles edges until negativity is removed

   Explanation: Johnson’s algorithm cleverly reweights all edges to remove negative weights without altering actual shortest paths. Cycling or repeating edges does not address negative weights. Ignoring negative edges produces incorrect results, and splitting edges is not part of the algorithm.

5. Efficiency with Sparse Graphs

   Which algorithm is typically more efficient for finding all-pairs shortest paths in large, sparse graphs?

   1. Depth-First Search
   2. Bellman-Ford algorithm
   3. Floyd-Warshall algorithm
   4. Johnson’s algorithm

   Explanation: Johnson’s algorithm is more efficient for sparse graphs thanks to its combination of reweighting and using Dijkstra's algorithm for each node. Floyd-Warshall has cubic complexity regardless of graph density. Bellman-Ford is slower for all-pairs, and Depth-First Search does not calculate path lengths suitable for this problem.

6. Detecting Negative Cycles

   Which step in the Floyd-Warshall algorithm can detect the presence of a negative weight cycle in the graph?

   1. Listing all possible paths
   2. Counting the total number of edges
   3. Checking the diagonal entries for negative values
   4. Comparing the initial and final adjacency matrices

   Explanation: After running Floyd-Warshall, negative values on the diagonal of the distance matrix indicate a negative cycle. Counting edges or comparing matrices does not detect negative cycles directly. Listing all possible paths is unnecessary for cycle detection.

7. Johnson’s Algorithm Initial Step

   What is the first major step in Johnson’s algorithm before running Dijkstra’s algorithm from each vertex?

   1. Add a new vertex connected to all others with zero-weight edges
   2. Reverse all the edges in the graph
   3. Label each vertex with its degree
   4. Replace all weights with their absolute values

   Explanation: The algorithm adds a new vertex, connecting it to every vertex with zero-weight edges, to facilitate reweighting via Bellman-Ford. Reversing edges or replacing weights changes the graph's structure, which is not required. Labeling by degree is not part of the Johnson’s approach.

8. Floyd-Warshall vs Dijkstra

   Compared to Dijkstra's algorithm, what is the main advantage of Floyd-Warshall for all-pairs shortest path problems?

   1. It only works with unweighted graphs
   2. It uses less memory for undirected graphs
   3. It runs faster for single-source problems
   4. It computes all-pairs shortest paths in a single execution

   Explanation: Floyd-Warshall is designed to deliver all shortest paths between every pair of nodes in one run. Dijkstra is more efficient for single-source cases. Memory usage is not necessarily less, and Floyd-Warshall works with weighted graphs, not solely unweighted graphs.

9. When to Avoid Floyd-Warshall

   In which scenario is Floyd-Warshall usually a poor choice for finding all-pairs shortest paths?

   1. A graph with only positive edge weights
   2. A small, densely connected graph
   3. A very large, sparse graph
   4. A graph with fewer than ten nodes

   Explanation: Floyd-Warshall's cubic time makes it inefficient on large, sparse graphs. For small or dense graphs, the running time is manageable. The algorithm supports positive edge weights and can handle small node counts effectively.

10. Result Interpretation in Floyd-Warshall

    After running Floyd-Warshall, what does a distance matrix entry of infinity (∞) between two vertices indicate?

    1. The vertices are part of the same strongly connected component
    2. No path exists between those vertices
    3. There is a direct edge between them
    4. A negative cycle is present between the vertices

    Explanation: An infinity in the result means that there is no reachable path from one vertex to another. Presence of a direct edge would yield a finite distance. A negative cycle would show up on the diagonal as a negative value, and strong connectivity does not guarantee absence of infinity between any two nodes.