Bellman-Ford algorithm in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Bellman-Ford algorithm used for?

The Bellman-Ford algorithm finds the shortest paths from a single starting point to all other points in a graph, even if some edges have negative weights.

beginner

How does Bellman-Ford handle negative edge weights?

Unlike some algorithms, Bellman-Ford can correctly find shortest paths even when edges have negative weights, as long as there are no negative weight cycles.

intermediate

What is a negative weight cycle and why is it important in Bellman-Ford?

A negative weight cycle is a loop in the graph where the total sum of edge weights is negative. Bellman-Ford detects these cycles because they make shortest paths undefined.

intermediate

How many times does Bellman-Ford relax edges in the graph?

Bellman-Ford relaxes all edges repeatedly for (number of vertices - 1) times to ensure shortest paths are found.

intermediate

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

The time complexity is O(V * E), where V is the number of vertices and E is the number of edges in the graph.

What type of graphs can Bellman-Ford algorithm work on?

A Only graphs with positive edge weights

B Graphs with negative edge weights but no negative cycles

C Only trees

D Graphs with negative cycles

Bellman-Ford works on graphs that may have negative edge weights but cannot have negative weight cycles.

How many times does Bellman-Ford relax edges in the worst case?

A E - 1 times

B E times

C V times

D V - 1 times

Bellman-Ford relaxes all edges (V - 1) times, where V is the number of vertices.

What does Bellman-Ford detect after relaxing edges (V - 1) times?

A If a negative weight cycle exists

B If the graph is connected

C If all edges are positive

D If the graph is a tree

After (V - 1) relaxations, Bellman-Ford checks for negative weight cycles by trying to relax edges once more.

Which of these algorithms cannot handle negative edge weights?

A Dijkstra's algorithm

B Breadth-first search

C Floyd-Warshall

D Bellman-Ford

Dijkstra's algorithm cannot handle negative edge weights correctly.

What is the main difference between Bellman-Ford and Dijkstra's algorithm?

A Both handle negative weights equally

B Dijkstra can handle negative weights; Bellman-Ford cannot

C Bellman-Ford can handle negative weights; Dijkstra cannot

D Bellman-Ford is faster than Dijkstra

Bellman-Ford can handle graphs with negative edge weights, while Dijkstra's algorithm cannot.

Explain how the Bellman-Ford algorithm finds shortest paths and detects negative weight cycles.

Think about how the algorithm updates distances and what happens if distances can still be improved after all relaxations.

Describe a real-life situation where using Bellman-Ford algorithm would be better than Dijkstra's algorithm.

Consider cases where costs can be negative and why detecting cycles matters.