Bellman Ford Algorithm

Rajiv Singh
1y
3.3k
0
2

Article

This is a C# implementation of the Bellman-Ford algorithm, which is used to find the shortest path from a single source vertex to all other vertices in a weighted graph. Here’s a breakdown of the code:

public class BellmanFord: This is the main class that contains all the other classes and methods.

public class Edge: This class represents an edge in the graph. It has three properties: src (source vertex), dest (destination vertex), and weight (weight of the edge).

public class Edge
{
    public int src, dest, weight;
}

public class Graph: This class represents a graph. It has three properties: V (number of vertices), E (number of edges), and edge (list of edges). It also has a method AddEdge(int src, int dest, int weight) to add an edge to the graph.

public class Graph
{
    public int V, E;
    public List<Edge> edge;

    public Graph(int V, int E)
    {
        this.V = V;
        this.E = E;
        this.edge = new List<Edge>();
    }

    public void AddEdge(int src, int dest, int weight)
    {
        Edge newEdge = new Edge { src = src, dest = dest, weight = weight };
        edge.Add(newEdge);
    }
}

static bool isNegCycleBellmanFord(Graph graph, int src, int[] dist): This method implements the Bellman-Ford algorithm. It takes as input a graph, a source vertex, and an array to store the shortest path distances. It returns true if there is a negative weight cycle in the graph reachable from the source and false otherwise.

static bool isNegCycleBellmanFord(Graph graph, int src, int[] dist)
{
    int V = graph.V;
    int E = graph.E;

    Array.Fill(dist, int.MaxValue);

    dist[src] = 0;
    int counts = 0;

    for (int i = 1; i <= V - 1; i++)
    {
        foreach (var edge in graph.edge)
        {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;

            if (dist[u] + weight < dist[v])
                dist[v] = Math.Min(dist[v], (dist[u] + weight));
        }

        counts++;
    }

    foreach (var edge in graph.edge)
    {
        int u = edge.src;
        int v = edge.dest;
        int weight = edge.weight;

        if (dist[u] + weight < dist[v])
            return true;
    }

    return false;
}

public static bool isNegCycleDisconnected(Graph graph): This method checks for a negative weight cycle in a disconnected graph. It iterates over all vertices, and for each unvisited vertex, it calls the isNegCycleBellmanFord() method. If any call returns true, it returns true; otherwise, it returns false.

public static bool isNegCycleDisconnected(Graph graph)
{
    int V = graph.V;

    bool[] visited = new bool[V + 1];
    int[] dist = new int[V + 1];

    for (int i = 1; i <= V; i++)
    {
        if (!visited[i])
        {
            if (isNegCycleBellmanFord(graph, i, dist))
                return true;

            for (int j = 0; j < V; j++)
            {
                if (dist[j] != int.MaxValue)
                    visited[j] = true;
            }
        }
    }

    return false;
}

The Bellman-Ford algorithm works by repeatedly relaxing edges in the graph. The relaxation process updates the shortest path distances if a shorter path is found. Suppose we can still relax edges after |V| - 1 iterations (where |V| is the number of vertices), then there is a negative weight cycle in the graph.

Let's take one example below and check if a graph contains a negative cycle.

public static void Main(String[] args)
{
    int V = 7, E = 10;
    BellmanFord.Graph graph = new BellmanFord.Graph(V, E);

    graph.AddEdge(1, 2, 6);
    graph.AddEdge(1, 3, 5);
    graph.AddEdge(1, 4, 5);
    graph.AddEdge(2, 5, -1);
    graph.AddEdge(3, 2, -2);
    graph.AddEdge(3, 5, 1);
    graph.AddEdge(4, 3, -2);
    graph.AddEdge(4, 6, -1);
    graph.AddEdge(5, 7, 3);
    graph.AddEdge(6, 7, 3);

    if (BellmanFord.isNegCycleDisconnected(graph))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}

This is the Main method of your program, which is the entry point for execution. Here’s what it does.

It creates a graph with 7 vertices and 10 edges.
It adds edges to the graph using the AddEdge method. The three arguments to this method are the source vertex, the destination vertex, and the weight of the edge.
It then calls the isNegCycleDisconnected method on the graph. This method checks if there is a negative weight cycle in the graph.
If there is a negative weight cycle, it prints “Yes” to the console; otherwise, it prints “No”.

The graph created in this code has the following edges (source -> destination [weight]):

1 -> 2 [6] 1 -> 3 [5] 1 -> 4 [5] 2 -> 5 [-1] 3 -> 2 [-2] 3 -> 5 [1] 4 -> 3 [-2] 4 -> 6 [-1] 5 -> 7 [3] 6 -> 7 [3]

The isNegCycleDisconnected method will return true if there is a negative weight cycle in this graph and false otherwise. A negative weight cycle is a cycle in which the sum of the weights of all the edges in the cycle is negative. The Bellman-Ford algorithm can detect such cycles. If such a cycle exists, then we can keep traversing the cycle to decrease the total cost of reaching some vertices. Hence no shortest path exists, and it returns “Yes”. Otherwise, “No”.

Bellman Ford