Bellman-Ford Algorithm

Bellman-Ford Algorithm
Runtime	$O(V^{2}+E)$
Class	Dynamic Programming Graph Algorithms Shortest Path Problem

Approach: dynamic programming

All shortest path must have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq |V| - 1 } edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

Recurrence

Let OPT(n-1, a) be the length of the shortest path from source node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} to node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} with at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n - 1} edges.

The idea is to add one edge at a time, seeing if the edge should be included in the shortest path.

If we don't add the edge, the length is OPT(n - 2, a)

If we add the edge, the length would be OPT(n - 2, b) + w(b, a)

OPT(a, n-1) = min(w(b,a) + OPT(n-1, b) for all (b, a) in E)

Implementation

Time complexity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^2 + VE) }

• Sparse: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^2) }
• Dense: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^3) }

// G: Graph with vertices (V) and edges (E)
// w[e]: weight of edge e
// S: starting node
Bellman-Ford(G, w, S)
    V, E = G
    pi[v] = null for all v  // traceback
    
    // initialize all shortest path algo
    d[v] = infty for all v
    d[s] = 0
    for i from 1 to |V| - 1:
        for all (u,v) in E
            if d[v] > d[u] + w(u, v):
                d[v] = d[u] + w(u,v)
                pi[v] = u;
    
    for all (u, v) in E:
        if d[v] > d[u] + w(u, v):
            // has negative cycle
            return false

This accounts for negative edges but not negative cycles. Bellman Ford can detect it by running an extra time, since if there is a negative cycle, the run time will improve.