Bellman Ford Algorithm Negative Weights in DSA C - Time & Space Complexity

Time Complexity: Bellman Ford Algorithm Negative Weights

O(V * E)

Understanding Time Complexity

We analyze how the Bellman Ford algorithm's running time grows with the size of the graph.

We want to know how the number of edges and vertices affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void bellmanFord(int V, int E, int edges[][3], int src, int dist[]) {
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j][0];
            int v = edges[j][1];
            int w = edges[j][2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
}
    

This code finds shortest paths from a source vertex to all others, even with negative weights.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop over all edges that relaxes distances.
• How many times: This inner loop runs for each vertex minus one times (V-1 times).

How Execution Grows With Input

The algorithm repeats checking all edges many times, so work grows with both vertices and edges.

Input Size (V, E)	Approx. Operations
V=10, E=20	About 9 * 20 = 180
V=100, E=500	About 99 * 500 = 49,500
V=1000, E=2000	About 999 * 2000 = 1,998,000

Pattern observation: Operations grow roughly by multiplying vertices and edges.

Final Time Complexity

Time Complexity: O(V * E)

This means the time grows by multiplying the number of vertices and edges in the graph.

Common Mistake

[X] Wrong: "The algorithm runs in O(V^2) time because it has two loops over vertices."

[OK] Correct: The inner loop runs over edges, not vertices, so the time depends on edges, not just vertices.

Interview Connect

Understanding this complexity helps you explain how Bellman Ford handles negative weights efficiently compared to other algorithms.

Self-Check

"What if we stopped the algorithm early when no distances change in an iteration? How would the time complexity change?"