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.