On this article, we’ll be taught C# implementation of Bellman–Ford Algorithm for figuring out the shortest paths from a single supply vertex to the entire different vertices in a weighted graph
utilizing System;
utilizing System.Collections.Generic;
utilizing System.Linq;
utilizing System.Textual content;
utilizing System.Diagnostics;
namespace BellmanFordAlgorithm
{
class BellmanFordAlgo
public struct Edge
public int Supply;
public int Vacation spot;
public int Weight;
public struct Graph
public int VerticesCount;
public int EdgesCount;
public Edge[] edge;
public static Graph CreateGraph(int verticesCount, int edgesCount)
Graph graph = new Graph();
graph.VerticesCount = verticesCount;
graph.EdgesCount = edgesCount;
graph.edge = new Edge[graph.EdgesCount];
return graph;
personal static void Print(int[] distance, int rely)
Console.WriteLine("Vertex Distance from supply");
for (int i = 0; i < rely; ++i)
Console.WriteLine("0t 1", i, distance[i]);
public static void BellmanFord(Graph graph, int supply)
int verticesCount = graph.VerticesCount;
int edgesCount = graph.EdgesCount;
int[] distance = new int[verticesCount];
for (int i = 0; i < verticesCount; i++)
distance[i] = int.MaxValue;
distance[source] = 0;
for (int i = 1; i <= verticesCount - 1; ++i)
for (int j = 0; j < edgesCount; ++j)
int u = graph.edge[j].Supply;
int v = graph.edge[j].Vacation spot;
int weight = graph.edge[j].Weight;
if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
distance[v] = distance[u] + weight;
for (int i = 0; i < edgesCount; ++i)
int u = graph.edge[i].Supply;
int v = graph.edge[i].Vacation spot;
int weight = graph.edge[i].Weight;
if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
Console.WriteLine("Graph incorporates detrimental weight cycle.");
Print(distance, verticesCount);
static void Major(string[] args)
int verticesCount = 5;
int edgesCount = 8;
Graph graph = CreateGraph(verticesCount, edgesCount);
// Edge 0-1
graph.edge[0].Supply = 0;
graph.edge[0].Vacation spot = 1;
graph.edge[0].Weight = -1;
// Edge 0-2
graph.edge[1].Supply = 0;
graph.edge[1].Vacation spot = 2;
graph.edge[1].Weight = 4;
// Edge 1-2
graph.edge[2].Supply = 1;
graph.edge[2].Vacation spot = 2;
graph.edge[2].Weight = 3;
// Edge 1-3
graph.edge[3].Supply = 1;
graph.edge[3].Vacation spot = 3;
graph.edge[3].Weight = 2;
// Edge 1-4
graph.edge[4].Supply = 1;
graph.edge[4].Vacation spot = 4;
graph.edge[4].Weight = 2;
// Edge 3-2
graph.edge[5].Supply = 3;
graph.edge[5].Vacation spot = 2;
graph.edge[5].Weight = 5;
// Edge 3-1
graph.edge[6].Supply = 3;
graph.edge[6].Vacation spot = 1;
graph.edge[6].Weight = 1;
// Edge 4-3
graph.edge[7].Supply = 4;
graph.edge[7].Vacation spot = 3;
graph.edge[7].Weight = -3;
BellmanFord(graph, 0);
}
Output:
Vertex Distance from supply
0 0
1 -1
2 2
3 -2
4 1
Thanks for visiting !!
© 2017, Csharp Star. All rights reserved.
