Bellman Ford

Introduction:

This is a single source shortest path Algorithm where there is a single source from which we want to find shortest path to a node or to all other nodes. Negative edges are allowed in the graph.This method is also used in negative weighted cycle detection in graphs.

Problem Statement:

find the shortest paths to all nodes from a start node.

Algorithm

1. A graph \(G(V, E)\) and start vertex \(s\) are given.

2. we have two arrays \(dist[\ ]\) initialized to \(\infty\) and \(prev[\ ]\) initilaized to -1 for all vertices

3. Relax all egdes ie., \(dist[v]\) .

4. Repeat above step \(|V|-1 \) times

5. Finally check step 3 again to see if there is any relaxation then there is a negative weighted cycle in the graph or else we get our shortest paths to all vertices from \(prev[\ ]\) and \(dist[\ ]\)

Pseudo code :

BellmanFord( G, s ):
    dist[G.num_vertices] := INFINITY
    prev[G.num_vertices] := -1
    dist[s] := 0

    repeat G.num_vertices - 1 times:
        repeat G.num_edges times:
            if dist[u] + w < dist[v]
            prev[v] = u

Code :

    // single source shortest path negative edges allowed
    #include <bits/stdc++.h>
    using namespace std;
    
    #define adjacency_list map<int, vector<pair<int, int>>>
    #define mp make_pair
    #define INF INT_MAX
    
    typedef struct edge
    {
        int u;
        int v;
        int w;
    } Edge;
    
    typedef struct graph
    {
        adjacency_list adj;
    
        int num_edges;
        int num_vertices;
        Edge *edge;
    } graph;
    
    void bellmanford(graph G, int source)
    {
        vector<int> dist(G.num_vertices, INF);
        vector<int> prev(G.num_vertices, -1);
    
        dist[source] = 0;
        for (int i = 0; i < G.num_vertices - 1; i++)
        {
            for (int j = 0; j < G.num_edges; j++)
            {
    
                int u = G.edge[j].u;
                int v = G.edge[j].v;
                int w = G.edge[j].w;
    
                if (dist[u] != INF && dist[u] + w < dist[v])
                {
                    dist[v] = dist[u] + w;
                    prev[v] = u;
                }
            }
        }
    
        cout << "vertex prev dist\n";
    
        for (int i = 0; i < G.num_vertices; i++)
        {
            cout << i << " " << prev[i] << " " << dist[i] << "\n";
        }
        // cout << "\n";
    }
    
    int main()
    {
        // undirected graph
    
        graph G; // u - {{v1,w1}, {v2, w2}, .... {vk,wk}}
        cin >> G.num_vertices;
        cin >> G.num_edges;
        G.edge = new Edge[G.num_edges];
        int u, v, w;
        for (int i = 0; i < G.num_edges; i++)
        {
            cin >> G.edge[i].u >> G.edge[i].v >> G.edge[i].w;
        }
        int s;
        cout << "Enter start vertext for bellmanford : ";
        cin >> s;
    
        bellmanford(G, s);
        // cout << "\n";
    }

Bellman Ford

Introduction:

Problem Statement:

Algorithm

Pseudo code :

Code :

Complexity Analysis :

video resources

web resources

book resources