Advanced Graph Algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall Quiz Quiz

Challenge your skills on advanced shortest path algorithms including Dijkstra, Bellman-Ford, and Floyd-Warshall. Assess your understanding of algorithm mechanics, use cases, and differences important for graph analysis and computational optimization.

1. Dijkstra's Algorithm Limitation

   Which type of weighted directed graph is unsuitable for finding shortest paths with Dijkstra's algorithm, for example, one containing a cycle with edge weights of -2, 3, and 4?

   1. Acyclic graphs with positive weights
   2. Undirected graphs only
   3. Graphs with negative edge weights
   4. Graphs where all weights are zero

   Explanation: Dijkstra's algorithm assumes all edge weights are non-negative, so negative weight edges can lead to incorrect results, especially in graphs with negative cycles. Acyclic graphs with positive weights and graphs where all weights are zero can be handled by Dijkstra's algorithm. Undirected graphs can work with Dijkstra’s as long as the weights are non-negative. Only the presence of negative weights disrupts its reliability.

2. Bellman-Ford Algorithm Output

   After applying the Bellman-Ford algorithm to a graph with a negative weight cycle reachable from the source, such as one with edges (A→B:2, B→C:-4, C→A:1), what result will it produce?

   1. Ignores negative weights and processes normally
   2. Returns incorrect positive distances
   3. All shortest path distances
   4. Detects negative cycle and aborts

   Explanation: Bellman-Ford can detect negative weight cycles during the relaxation process. If such a cycle is reachable from the source, it indicates the presence and typically halts or reports an error. It won't compute correct shortest paths in this scenario. Unlike Dijkstra’s, it does not ignore negative weights, and returning all distances is only correct when all cycles have non-negative total weight.

3. Floyd-Warshall Use Case

   For which type of problem is the Floyd-Warshall algorithm particularly suited, for instance, calculating shortest paths between every pair of cities in a country?

   1. Single-source shortest path
   2. All-pairs shortest path
   3. Minimum spanning tree
   4. Single-destination shortest path

   Explanation: Floyd-Warshall is specifically designed for finding shortest paths between all pairs of vertices in a weighted graph, making it ideal for scenarios like city-to-city route evaluation. Single-source or single-destination problems are better solved by Dijkstra or Bellman-Ford. Minimum spanning tree problems are unrelated and require different algorithms entirely.

4. Edge Relaxation Comparison

   How does the edge relaxation step differ between Dijkstra’s and Bellman-Ford algorithms, specifically in the way they revisit edges?

   1. Dijkstra relaxes each edge once; Bellman-Ford may relax repeatedly
   2. Dijkstra may relax edges multiple times; Bellman-Ford only once
   3. Bellman-Ford never revisits edges
   4. Both relax each edge only once

   Explanation: Dijkstra's algorithm selects the shortest current path and relaxes outgoing edges only once per vertex. Bellman-Ford can relax the same edge multiple times in multiple passes to account for negative cycles or paths. The options suggesting both algorithms relax edges only once or that Bellman-Ford never revisits edges are inaccurate.

5. Memory Complexity of Floyd-Warshall

   What is the memory complexity for storing intermediate distances in the Floyd-Warshall algorithm when run on a graph with n vertices?

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

   Explanation: Floyd-Warshall uses an n by n matrix to store shortest distances between every vertex pair, resulting in O(n^2) memory usage. The O(n^3) term relates to time complexity, not memory. O(n) and O(n log n) are too low for the matrix needed to store all-pairs distances.