Virtual Labs

Bellman-Ford Algorithm for Single Source Shortest Path

What is the primary purpose of the Bellman-Ford algorithm?

a: To detect all cycles in a graph Explanation

Explanation

b: To perform topological sorting on a directed graph Explanation

Explanation

c: To find the minimum spanning tree of a graph Explanation

Explanation

d: To find shortest paths from a source vertex to all other vertices Explanation

Explanation

What is the time complexity of the Bellman-Ford algorithm?

a: O(V log V) where V is the number of vertices Explanation

Explanation

b: O(E log V) where E is edges and V is vertices Explanation

Explanation

c: O(V × E) where V is vertices and E is edges Explanation

Explanation

d: O(V²) where V is the number of vertices Explanation

Explanation

Which type of edge weights can the Bellman-Ford algorithm handle that Dijkstra's algorithm cannot?

a: Positive edge weights Explanation

Explanation

b: Zero edge weights Explanation

Explanation

c: Negative edge weights Explanation

Explanation

d: Fractional edge weights Explanation

Explanation

In the standard (naive, without early termination) Bellman-Ford algorithm, how many times are all edges relaxed?

a: E times, where E is the number of edges Explanation

Explanation

b: V times, where V is the number of vertices Explanation

Explanation

c: V - 1 times, where V is the number of vertices Explanation

Explanation

d: Until no more updates are possible Explanation

Explanation

In the Bellman-Ford algorithm, what does 'relaxing an edge' mean?

a: Checking if a shorter path exists through that edge and updating distances if so Explanation

Explanation

b: Removing the edge from the graph temporarily Explanation

Explanation

c: Decreasing the weight of the edge Explanation

Explanation

d: Marking the edge as visited Explanation

Explanation

What happens if you run one more iteration (the V-th iteration) after the standard V-1 iterations?

a: It has no purpose and is redundant Explanation

Explanation

b: It optimizes the solution further Explanation

Explanation

c: It resets all distances to infinity Explanation

Explanation

d: It allows detection of negative weight cycles Explanation

Explanation

If a graph has 6 vertices and 10 edges, what is the maximum number of edge relaxation operations performed by Bellman-Ford?

a: 10 Explanation

Explanation

b: 60 Explanation

Explanation

c: 50 Explanation

Explanation

d: 100 Explanation

Explanation

Consider a graph with edges: A→B (weight 5), B→C (weight -3), C→D (weight 2), A→D (weight 8). Starting from A, what is the shortest distance to D?

a: 4 Explanation

Explanation

b: 8 Explanation

Explanation

c: 6 Explanation

Explanation

d: 5 Explanation

Explanation

Which statement about negative weight cycles is TRUE?

a: Bellman-Ford can find shortest paths even when negative cycles are reachable from the source Explanation

Explanation

b: Dijkstra's algorithm can handle negative cycles better than Bellman-Ford Explanation

Explanation

c: Negative cycles always increase the shortest path distances Explanation

Explanation

d: Negative cycles make the shortest path problem undefined for affected vertices Explanation

Explanation

What is the initial distance assigned to the source vertex in Bellman-Ford?

a: Infinity (∞) Explanation

Explanation

b: 0 Explanation

Explanation

c: -1 Explanation

Explanation

d: The number of vertices Explanation

Explanation