Bellman-Ford Algorithm

Definition

Definition

The Bellman-Ford Algorithm is a dynamic programming algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph, even if the graph contains negative weight edges (as long as there are no negative weight cycles)

Explanation

Repeatedly relaxing edges, updating the shortest path estimates until they converge to the optimal solution

Guidance

• Initialization
  • set the distance to the source vertex as 0 and all other vertices as infinity
• Iterative Relaxation (Repeat V-1 times)
  • for each edge (u, v) in the graph
    • if the distance to v through u is shorter than the current distance to v
      • update the distance to v as the distance to u plus the weight of edge (u, v)
• Check for Negative Cycles
  • after V-1 iterations
    • check each edge (u, v) in the graph
      • if the distance to v can still be decreased, then there exists a negative weight cycle
• Output
  • return the shortest distances calculated from the source vertex to all other vertices

Tips

• keep track of the minimum distances and update them iteratively
• handle negative weight cycles separately as they can cause the algorithm to enter an infinite loop
• be cautious about the complexity, as the algorithm can become inefficient for large graphs with many edges

Practice

Practice

function findArticulationPoints(graph):
  # Initialize variables and data structures
  articulationPoints = []
  visited = {}
  discoveryTime = {}
  low = {}
  parent = {}
  time = 0

  # Perform DFS traversal
  for each vertex in graph.vertices():
    if vertex not in visited:
      dfs(vertex, visited, discoveryTime, low, parent, articulationPoints, time)

  return articulationPoints

function dfs(vertex, visited, discoveryTime, low, parent, articulationPoints, time):
  # Mark vertex as visited and set its discovery time
  visited[vertex] = True
  time += 1
  discoveryTime[vertex] = time
  low[vertex] = time
  children = 0

  # Iterate over adjacent vertices
  for each neighbor in graph.neighbors(vertex):
    if neighbor not in visited:
      # Update parent of neighbor
      parent[neighbor] = vertex
      children += 1
      dfs(neighbor, visited, discoveryTime, low, parent, articulationPoints, time)

      # Update low value of vertex
      low[vertex] = min(low[vertex], low[neighbor])

      # Check if vertex is an articulation point
      if parent[vertex] is None and children > 1:
        articulationPoints.append(vertex)
      elif parent[vertex] is not None and low[neighbor] >= discoveryTime[vertex]:
        articulationPoints.append(vertex)
    elif neighbor != parent[vertex]:
      # Update low value of vertex if neighbor is not parent
      low[vertex] = min(low[vertex], discoveryTime[neighbor])

Solution

package main

import (
    "math"
)

type Edge struct {
    src, dest, weight int
}

func bellmanFord(graph []Edge, V, E, src int) {
    dist := make([]int, V)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[src] = 0

    for i := 1; i < V; i++ {
        for j := 0; j < E; j++ {
            u := graph[j].src
            v := graph[j].dest
            weight := graph[j].weight
            if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
                dist[v] = dist[u] + weight
            }
        }
    }

    for _, edge := range graph {
        u := edge.src
        v := edge.dest
        weight := edge.weight
        if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
            fmt.Println("Graph contains negative weight cycle")
            return
        }
    }

    fmt.Println("Vertex Distance from Source:")
    for i := 0; i < V; i++ {
        fmt.Printf("Vertex %d --> Distance %d\n", i, dist[i])
    }
}

import java.util.Arrays;

class BellmanFord {

  int V, E;

  ;
  Edge edge[];
  BellmanFord(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[e];
    for (int i = 0; i < e; ++i) {
      edge[i] = new Edge();
    }
  }

  void BellmanFordAlgo(BellmanFord graph, int src) {
    int V = graph.V, E = graph.E;
    int dist[] = new int[V];

    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int i = 1; i < V; ++i) {
      for (int j = 0; j < E; ++j) {
        int u = graph.edge[j].src;
        int v = graph.edge[j].dest;
        int weight = graph.edge[j].weight;
        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
          dist[v] = dist[u] + weight;
        }
      }
    }

    for (int j = 0; j < E; ++j) {
      int u = graph.edge[j].src;
      int v = graph.edge[j].dest;
      int weight = graph.edge[j].weight;
      if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
        System.out.println("Graph contains negative weight cycle");
      }
    }

    System.out.println("Vertex Distance from Source");
    for (int i = 0; i < V; ++i) {
      System.out.println(i + "\t\t" + dist[i]);
    }
  }

  class Edge {

    int src, dest, weight;

    Edge() {
      src = dest = weight = 0;
    }
  }
}

function BellmanFord(graph, V, E, src) {
  let dist = new Array(V).fill(Number.MAX_SAFE_INTEGER);
  dist[src] = 0;

  for (let i = 1; i < V; i++) {
    for (let j = 0; j < E; j++) {
      let u = graph[j].src;
      let v = graph[j].dest;
      let weight = graph[j].weight;
      if (dist[u] != Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
      }
    }
  }

  for (let j = 0; j < E; j++) {
    let u = graph[j].src;
    let v = graph[j].dest;
    let weight = graph[j].weight;
    if (dist[u] != Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) {
      console.log("Graph contains negative weight cycle");
      return;
    }
  }

  console.log("Vertex Distance from Source:");
  for (let i = 0; i < V; i++) {
    console.log(i + "\t\t" + dist[i]);
  }
}

class Edge(val src: Int, val dest: Int, val weight: Int)

fun bellmanFord(graph: List<Edge>, V: Int, E: Int, src: Int) {
    val dist = IntArray(V) { Int.MAX_VALUE }
    dist[src] = 0

    for (i in 1 until V) {
        for (j in 0 until E) {
            val u = graph[j].src
            val v = graph[j].dest
            val weight = graph[j].weight
            if (dist[u] != Int.MAX_VALUE && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight
            }
        }
    }

    for (j in 0 until E) {
        val u = graph[j].src
        val v = graph[j].dest
        val weight = graph[j].weight
        if (dist[u] != Int.MAX_VALUE && dist[u] + weight < dist[v]) {
            println("Graph contains negative weight cycle")
            return
        }
    }

    println("Vertex Distance from Source:")
    for (i in 0 until V) {
        println("$i \t\t ${dist[i]}")
    }
}

def bellman_ford(graph, V, E, src):
    dist = [float("Inf")] * V
    dist[src] = 0

    for _ in range(V - 1):
        for u, v, weight in graph:
            if dist[u] != float("Inf") and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight

    for u, v, weight in graph:
        if dist[u] != float("Inf") and dist[u] + weight < dist[v]:
            print("Graph contains negative weight cycle")
            return

    print("Vertex Distance from Source")
    for i in range(V):
        print(f"{i}\t\t{dist[i]}")

use std::cmp::Ordering;

#[derive(Clone, Copy)]
struct Edge {
    src: usize,
    dest: usize,
    weight: i32,
}

impl Edge {
    pub fn new(src: usize, dest: usize, weight: i32) -> Self {
        Edge { src, dest, weight }
    }
}

fn bellman_ford(graph: &Vec<Edge>, v: usize, e: usize, src: usize) {
    let mut dist: Vec<i32> = vec![i32::MAX; v];
    dist[src] = 0;

    for _ in 1..v {
        for j in 0..e {
            let u = graph[j].src;
            let v = graph[j].dest;
            let weight = graph[j].weight;
            if dist[u] != i32::MAX && dist[u] + weight < dist[v] {
                dist[v] = dist[u] + weight;
            }
        }
    }

    for j in 0..e {
        let u = graph[j].src;
        let v = graph[j].dest;
        let weight = graph[j].weight;
        if dist[u] != i32::MAX && dist[u] + weight < dist[v] {
            println!("Graph contains negative weight cycle");
            return;
        }
    }

    println!("Vertex Distance from Source:");
    for i in 0..v {
        println!("{} \t\t {}", i, dist[i]);
    }
}

class Edge {
  src: number;
  dest: number;
  weight: number;

  constructor(src: number, dest: number, weight: number) {
    this.src = src;
    this.dest = dest;
    this.weight = weight;
  }
}

function bellmanFord(graph: Edge[], V: number, E: number, src: number): void {
  let dist: number[] = Array(V).fill(Number.MAX_SAFE_INTEGER);
  dist[src] = 0;

  for (let i = 1; i < V; i++) {
    for (let j = 0; j < E; j++) {
      let u: number = graph[j].src;
      let v: number = graph[j].dest;
      let weight: number = graph[j].weight;
      if (dist[u] != Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
      }
    }
  }

  for (let j = 0; j < E; j++) {
    let u: number = graph[j].src;
    let v: number = graph[j].dest;
    let weight: number = graph[j].weight;
    if (dist[u] != Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) {
      console.log("Graph contains negative weight cycle");
      return;
    }
  }

  console.log("Vertex Distance from Source:");
  for (let i = 0; i < V; i++) {
    console.log(i + "\t\t" + dist[i]);
  }
}