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]()
The Time Complexity will be: O(V * E)
- V: No. of vertices.
- E: No. of edges.