Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Tuesday, June 23

    Bellman Ford Algorithm Code

    Updated: Algorithms No Comments3 Mins Readdevangini123By

    Code

      function bellmanFord(edges, V, src) {
    const dist = new Array(V).fill(Infinity);
    dist[src] = 0;

    // Relax edges V-1 times
    for (let i = 0; i < V - 1; i++) {
        let updated = false;

        for (let [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }

        // Early stopping if no update happened
        if (!updated) break;
    }

    // Check for negative weight cycle
    for (let [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
            console.log("Negative Weight cycle Detected");
            return null;
        }
    }

    return dist;
}

// Edge list: [u, v, w]
const edges = [
    [0, 1, 6],
    [0, 2, 5],
    [0, 3, 5],
    [1, 4, -1],
    [2, 1, -2],
    [2, 4, 1],
    [3, 2, -2],
    [3, 5, -1],
    [4, 6, 3],
    [5, 6, 3]
];

// Example for negative cycle case
/*
const edges = [
    [0, 1, 4],
    [1, 2, -1],
    [2, 3, -2],
    [3, 1, 0]
];
*/

const V = 7;
console.log(bellmanFord(edges, V, 0));
    
        def bellman_ford(edges, V, src):
    dist = [float('inf')] * V
    dist[src] = 0

    # Relax edges V-1 times
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # Check for negative weight cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            print("Negative Weight cycle Detected")
            return None

    return dist


edges = [
    (0, 1, 6),
    (0, 2, 5),
    (0, 3, 5),
    (1, 4, -1),
    (2, 1, -2),
    (2, 4, 1),
    (3, 2, -2),
    (3, 5, -1),
    (4, 6, 3),
    (5, 6, 3)
]

V = 7
print(bellman_ford(edges, V, 0))

    
    import java.util.*;
   class Solution {
    static int[] bellmanFord(int[][] edges, int V, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int i = 0; i < V - 1; i++) {
            boolean updated = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                System.out.println("Negative Weight cycle Detected");
                return null;
            }
        }
        return dist;
    }
    public static void main(String[] args) {
        int[][] edges = {
            {0, 1, 6},
            {0, 2, 5},
            {0, 3, 5},
            {1, 4, -1},
            {2, 1, -2},
            {2, 4, 1},
            {3, 2, -2},
            {3, 5, -1},
            {4, 6, 3},
            {5, 6, 3}
        };
        int V = 7;
        System.out.println(Arrays.toString(bellmanFord(edges, V, 0)));
    }
}
    
    #include <bits/stdc++.h>
using namespace std;

vector bellmanFord(vector>& edges, int V, int src) {
    vector dist(V, INT_MAX);
    dist[src] = 0;

    for (int i = 0; i < V - 1; i++) {
        bool updated = false;
        for (auto &e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }

    for (auto &e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            cout << "Negative Weight cycle Detected" << endl;
            return {};
        }
    }
    return dist;
}

int main() {
    vector> edges = {
        {0,1,6},{0,2,5},{0,3,5},{1,4,-1},
        {2,1,-2},{2,4,1},{3,2,-2},
        {3,5,-1},{4,6,3},{5,6,3}
    };

    int V = 7;
    vector res = bellmanFord(edges, V, 0);
    for (int x : res) cout << x << " ";
}

  
    #include <stdio.h>
#include <limits.h>

typedef struct {
    int u, v, w;
} Edge;

int main() {
    int V = 7, E = 10, src = 0;
    Edge edges[] = {
        {0,1,6},{0,2,5},{0,3,5},{1,4,-1},
        {2,1,-2},{2,4,1},{3,2,-2},
        {3,5,-1},{4,6,3},{5,6,3}
    };

    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (int i = 0; i < V - 1; i++) {
        int updated = 0;
        for (int j = 0; j < E; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            int w = edges[j].w;

            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = 1;
            }
        }
        if (!updated) break;
    }

    for (int j = 0; j < E; j++) {
        int u = edges[j].u;
        int v = edges[j].v;
        int w = edges[j].w;

        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Negative Weight cycle Detected\n");
            return 0;
        }
    }

    for (int i = 0; i < V; i++)
        printf("%d ", dist[i]);

    return 0;
}

    using System;

class Solution {
    static int[] BellmanFord(int[,] edges, int V, int src) {
        int[] dist = new int[V];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;

        int E = edges.GetLength(0);

        for (int i = 0; i < V - 1; i++) {
            bool updated = false;
            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.MaxValue && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }

        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.MaxValue && dist[u] + w < dist[v]) {
                Console.WriteLine("Negative Weight cycle Detected");
                return null;
            }
        }
        return dist;
    }

    static void Main() {
        int[,] edges = {
            {0,1,6},{0,2,5},{0,3,5},{1,4,-1},
            {2,1,-2},{2,4,1},{3,2,-2},
            {3,5,-1},{4,6,3},{5,6,3}
        };

        int V = 7;
        var res = BellmanFord(edges, V, 0);
        if (res != null)
            Console.WriteLine(string.Join(" ", res));
    }
}

    Time Complexity: O(V x E) = O(n2)

    If we assume: V = n and E = n

    Space Complexity: O(V)

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us