Shortest Path Algorithms: Dijkstra and Bellman-Ford Quiz Quiz

Challenge your understanding of shortest path algorithms, focusing on Dijkstra and Bellman-Ford. This quiz covers algorithm principles, use cases, limitations, and key differences to help you master important graph theory concepts.

1. Basic Principle of Dijkstra’s Algorithm

   Which type of edge weights can Dijkstra’s algorithm handle correctly when finding shortest paths in a graph?

   1. Zero-weight edges only
   2. Non-negative edge weights only
   3. Mixed positive and negative edge weights
   4. Negative edge weights only

   Explanation: Dijkstra’s algorithm is designed to work with non-negative edge weights, as negative weights can lead the algorithm to make incorrect path selections. It cannot handle negative edge weights safely because it might reach an already visited node with a lower cost later, violating its assumptions. While it can process zero-weight edges (since zero is non-negative), it cannot handle negative edges or a mix of positives and negatives. Negative edge weights and mixed graphs can lead to incorrect shortest paths with Dijkstra’s method.

2. Bellman-Ford Algorithm Capabilities

   What unique feature does the Bellman-Ford algorithm offer compared to Dijkstra’s algorithm?

   1. It can detect negative weight cycles in a graph
   2. It only works for undirected graphs
   3. It always runs faster on all graphs
   4. It cannot handle graphs with zero-weight edges

   Explanation: Bellman-Ford has the significant advantage of detecting negative weight cycles, something Dijkstra’s algorithm cannot do. While Bellman-Ford is generally slower, it is not always faster than Dijkstra’s algorithm. It works with both directed and undirected graphs, not just undirected ones, and it can handle zero-weight edges alongside other weights.

3. Graph Representation in Dijkstra’s Algorithm

   When implementing Dijkstra’s algorithm efficiently on a large graph, which data structure is most commonly used to select the next vertex with the minimal tentative distance?

   1. Priority queue
   2. Stack
   3. Simple array
   4. Hash table

   Explanation: A priority queue allows Dijkstra’s algorithm to efficiently select the node with the smallest current distance, improving overall runtime. A simple array would need a full scan for each selection, and a stack does not support the necessary ordering. A hash table cannot efficiently maintain elements by order of value, making it unsuitable for this purpose.

4. Time Complexity Comparison

   What is the time complexity of Dijkstra’s algorithm when using a binary heap as the priority queue for a graph with V vertices and E edges?

   1. O(VE)
   2. O(E^2)
   3. O(V^2)
   4. O((V + E) log V)

   Explanation: With a binary heap, Dijkstra’s algorithm achieves a time complexity of O((V + E) log V), improving over the naive O(V^2) version. The O(VE) complexity is associated with Bellman-Ford, not Dijkstra’s heap-based approach. O(E^2) does not apply for these algorithms, and O(V^2) only applies with simpler implementations.

5. Negative Weight Cycle Impact

   If a graph contains a negative weight cycle, how does the Bellman-Ford algorithm respond?

   1. It reports the existence of a negative weight cycle
   2. It only processes positive edges
   3. It completes normally with correct results
   4. It returns incorrect shortest path distances

   Explanation: Bellman-Ford’s ability to detect and report negative weight cycles is one of its defining features, thereby preventing the output of incorrect shortest paths. Instead of giving incorrect results or ignoring the cycle, it will report an error. It does not limit itself to processing only positive edges and won't complete normally if a negative cycle is present.

6. Initialization Step for Both Algorithms

   At the beginning of both Dijkstra’s and Bellman-Ford algorithms, how are the initial path estimates from the source to all other nodes set?

   1. Negative infinity for all nodes
   2. Zero for all nodes
   3. Infinity except for the source node, which is zero
   4. One for all nodes including the source

   Explanation: Both algorithms start by setting the distance to the source node as zero and all other nodes as infinity, ensuring that no node appears reachable until found to be so. Setting all distances to zero or one would not allow for correct path computation, and negative infinity would break the algorithms’ logic.

7. Cycle Handling in Dijkstra’s Algorithm

   If the input graph for Dijkstra's algorithm contains cycles with non-negative weights, what effect will these cycles have on the outcome?

   1. It will only work if cycles are removed
   2. The algorithm will fail to terminate
   3. The shortest path will still be found correctly
   4. The shortest path cannot be found

   Explanation: Dijkstra’s algorithm handles non-negative weighted cycles by still finding the shortest path, as revisiting nodes through cycles cannot give a lower cost. The presence of cycles does not prevent it from terminating or finding the correct answer. There is no need to remove cycles if they only have non-negative weights.

8. Algorithm Choice for Real-time Navigation

   Which algorithm would be more suitable for routing in real-time navigation systems where all edge weights are guaranteed to be non-negative?

   1. Depth-First Search (DFS)
   2. Bellman-Bord algorithm
   3. Dikstrap’s algorithm
   4. Dijkstra’s algorithm

   Explanation: Because real-time navigation benefits from both speed and accuracy, and all edges are non-negative, Dijkstra’s algorithm is preferred for its efficiency. The so-called Bellman-Bord and Dikstrap’s algorithms are not standard (the names are intentionally misspelled distractors), and DFS is not designed for shortest-path problems.

9. Scenario When Bellman-Ford Is Preferred

   Consider a graph with some edges having negative weights but no negative weight cycles. Which algorithm would be most reliable for finding shortest paths from a single source in this case?

   1. Topological sorting
   2. Breath-First Search
   3. Dijkstra's algorithm
   4. Bellman-Ford algorithm

   Explanation: The Bellman-Ford algorithm is reliable for graphs with negative edge weights, as long as there are no negative cycles. Dijkstra's algorithm can produce incorrect results in such cases. Breath-First Search and topological sorting are not used for shortest-path finding in weighted graphs.

10. Relaxation Step Purpose

    What is the purpose of the relaxation step in both Dijkstra’s and Bellman-Ford algorithms?

    1. To remove cycles from the graph
    2. To reverse all edges
    3. To update the shortest known distance to each vertex
    4. To re-weight the graph edges

    Explanation: Relaxation is the process of checking and updating the estimated shortest distance to a vertex if a shorter path is found. It does not remove cycles or reverse edges; nor does it change the weights assigned to edges. Only updating shortest known distances reflects the true purpose of the relaxation step.