Bellman Ford Algorithm Negative Weights in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of the Bellman Ford algorithm?

It finds the shortest paths from a single source vertex to all other vertices in a weighted graph, even if some edge weights are negative.

intermediate

How does Bellman Ford handle negative weight edges differently from Dijkstra's algorithm?

Bellman Ford can correctly process graphs with negative weight edges by relaxing edges multiple times, while Dijkstra's algorithm assumes all weights are non-negative and may fail with negative edges.

beginner

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.

intermediate

What does it mean if Bellman Ford detects a negative weight cycle?

It means there is a cycle in the graph where the total sum of edge weights is negative, causing infinite reduction of path cost, so shortest paths are undefined.

beginner

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

It relaxes all edges exactly V-1 times, where V is the number of vertices, to ensure shortest paths are found.

What is the first step in the Bellman Ford algorithm?

A Relax edges only once

B Sort all edges by weight

C Detect negative weight cycles immediately

D Initialize distances from source to all vertices as infinity except source itself as zero

Bellman Ford starts by setting the source distance to zero and all others to infinity.

How does Bellman Ford detect a negative weight cycle?

A By running Dijkstra's algorithm first

B By sorting edges and finding cycles

C By checking if any edge can still be relaxed after V-1 iterations

D By counting the number of vertices

If after V-1 relaxations, an edge can still be relaxed, a negative cycle exists.

What is the maximum number of times edges are relaxed in Bellman Ford?

A V-1 times

B E times

C V times

D E-1 times

Edges are relaxed V-1 times to guarantee shortest paths.

Which of these graphs is Bellman Ford best suited for?

A Graphs with negative weights but no negative cycles

B Graphs with only positive weights

C Graphs with negative cycles

D Unweighted graphs

Bellman Ford works well with negative weights but cannot produce shortest paths if negative cycles exist.

What happens if Bellman Ford finds a negative weight cycle?

A It returns shortest paths ignoring the cycle

B It reports that shortest paths are undefined

C It stops and returns partial results

D It converts negative weights to positive

Negative cycles mean shortest paths cannot be defined, so the algorithm reports this.

Explain how the Bellman Ford algorithm finds shortest paths in graphs with negative weights.

Think about repeated edge relaxation and cycle detection.

Describe how Bellman Ford detects negative weight cycles and why this is important.

Focus on the final check after all relaxations.