Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Bellman Ford algorithm helps to find the shortest path
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace Rextester { public class Program { public static void Main(string[] args) { /* Bellman Ford algorithm helps us find the shortest path from a vertex to all other vertices of a weighted graph. It is similar to Dijkstra's algorithm but it can work with graphs in which edges can have negative weights. Solves single shortest path problem in which edge weight may be negative but no negative cycle exists. This algorithm works correctly when some of the edges of the directed graph G may have negative weight. When there are no cycles of negative weight, then we can find out the shortest path between source and destination. It is slower than Dijkstra's Algorithm but more versatile, as it capable of handling some of the negative weight edges. */ int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph Graph graph = new Graph(V, E); // add edge 0 -> 1 graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // add edge 0 -> 2 graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // add edge 1 -> 2 graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // add edge 1 -> 3 graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // add edge 1 -> 4 graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // add edge 3 -> 2 graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // add edge 3 -> 1 graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // add edge 4 -> 3 graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; graph.BellmanFord(graph, 0); } } // A class to represent a connected, directed and weighted graph public class Graph { // A class to represent a weighted edge in graph public class Edge { public int src, dest, weight; public Edge() { src = dest = weight = 0; } }; int VerticesCount, EdgesCount; public Edge[] edge; // Creates a graph with vertices and edges public Graph(int verticesCount, int edgesCount) { this.VerticesCount = verticesCount; this.EdgesCount = edgesCount; edge = new Edge[edgesCount]; for (int indx = 0; indx < edgesCount; ++indx) { edge[indx] = new Edge(); } } // It finds shortest distances from src to all other vertices using Bellman-Ford algorithm. // It also detects negative weight cycle public void BellmanFord(Graph graph, int src) { int verticesCount = graph.VerticesCount; int edgesCount = graph.EdgesCount; int[] dist = new int[verticesCount]; // Step 1: Initialize distances array from src vertex to all other vertices as INFINITE for (int indx = 0; indx < verticesCount; ++indx) { dist[indx] = int.MaxValue; } // mark the source vertex dist[src] = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < verticesCount; ++i) { for (int j = 0; j < edgesCount; ++j) { //get the edge data int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } //step 3: detect negative cycle if value changes then we have a negative cycle in the graph and we cannot find the shortest distances for (int j = 0; j < edgesCount; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) { Console.WriteLine("Graph contains negative weight cycle."); return; } } //No negative weight cycle found! print the distance and predecessor array display(dist, verticesCount, src); } // Display the solution public void display(int[] dist, int verticesCount, int src) { Console.WriteLine("Vertex Distance from Source vertex : {0}" , src); Console.WriteLine(); for (int i = 0; i < verticesCount; ++i) Console.WriteLine( "shortest path from the vertex " + src + " to " + i + " : \t " + dist[i]); } } }
run
|
edit
|
history
|
help
0
Список Лекарств
test
Великий и могучий РУСЯЗ
asxsdf
Min Max Sum Avg
Captcha
C# - out parameters and reference parameters
services
Func
Print 2D Array