beginner

What problem does the Bellman Ford algorithm solve?

It finds the shortest path from a single source vertex to all other vertices in a weighted graph, even if some edges have negative weights.

Click to reveal answer

beginner

Why can Dijkstra's algorithm fail with negative edge weights?

Because it assumes that once a vertex's shortest path is found, it cannot be improved. Negative weights can reduce path costs later, breaking this assumption.

Click to reveal answer

intermediate

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 in the graph.

Click to reveal answer

intermediate

What does Bellman Ford do to detect negative weight cycles?

After |V| - 1 relaxations, it checks all edges one more time. If any edge can still be relaxed, it means a negative weight cycle exists.

Click to reveal answer

beginner

What is the time complexity of the Bellman Ford algorithm?

O(|V| * |E|), where |V| is the number of vertices and |E| is the number of edges.

Click to reveal answer

What is the main advantage of Bellman Ford over Dijkstra's algorithm?

AIt only works on unweighted graphs

BIt works with graphs that have negative edge weights

CIt uses less memory

DIt is faster for all graphs

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

A|V| times

B|E| times

C|V| - 1 times

DOnce

What does it mean if Bellman Ford can still relax an edge after |V| - 1 iterations?

AThere is a negative weight cycle

BGraph is disconnected

CAll shortest paths are found

DGraph has no edges

Which data structure is primarily used to represent the graph in Bellman Ford?

AEdge list

BAdjacency list

CAdjacency matrix

DStack

What is the time complexity of Bellman Ford algorithm?

AO(|V| + |E|)

BO(|E|^2)

CO(|V|^2)

DO(|V| * |E|)

Explain how Bellman Ford algorithm detects negative weight cycles.

Describe the step-by-step process of the Bellman Ford algorithm for finding shortest paths.