C-Sharp/Algorithms/Graph/BellmanFord.cs at master · TheAlgorithms/C-Sharp · GitHub

Name: C-Sharp/Algorithms/Graph/BellmanFord.cs at master · TheAlgorithms/C-Sharp · GitHub
Rating: 4.6 (4409 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
usingSystem;
usingSystem.Collections.Generic;
usingDataStructures.Graph;

namespaceAlgorithms.Graph;

/// <summary>
/// Bellman-Ford algorithm on directed weighted graph.
/// </summary>
/// <typeparam name="T">Generic type of data in the graph.</typeparam>
publicclassBellmanFord<T>
{
privatereadonlyDirectedWeightedGraph<T>graph;
privatereadonlyDictionary<Vertex<T>,double>distances;
privatereadonlyDictionary<Vertex<T>,Vertex<T>?>predecessors;

publicBellmanFord(DirectedWeightedGraph<T>graph,Dictionary<Vertex<T>,double>distances,Dictionary<Vertex<T>,Vertex<T>?>predecessors)
{
this.graph=graph;
this.distances=distances;
this.predecessors=predecessors;
}

/// <summary>
/// Runs the Bellman-Ford algorithm to find the shortest distances from the source vertex to all other vertices.
/// </summary>
/// <param name="sourceVertex">Source vertex for shortest path calculation.</param>
/// <returns>
/// A dictionary containing the shortest distances from the source vertex to all other vertices.
/// If a vertex is unreachable from the source, it will have a value of double.PositiveInfinity.
/// </returns>
publicDictionary<Vertex<T>,double>Run(Vertex<T>sourceVertex)
{
InitializeDistances(sourceVertex);
RelaxEdges();
CheckForNegativeCycles();
returndistances;
}

privatevoidInitializeDistances(Vertex<T>sourceVertex)
{
foreach(varvertexingraph.Vertices)
{
if(vertex!=null)
{
distances[vertex]=double.PositiveInfinity;
predecessors[vertex]=null;
}
}

distances[sourceVertex]=0;
}

privatevoidRelaxEdges()
{
intvertexCount=graph.Count;

for(inti=0;i<vertexCount-1;i++)
{
foreach(varvertexingraph.Vertices)
{
if(vertex!=null)
{
RelaxEdgesForVertex(vertex);
}
}
}
}

privatevoidRelaxEdgesForVertex(Vertex<T>u)
{
foreach(varneighboringraph.GetNeighbors(u))
{
if(neighbor==null)
{
continue;
}

varv=neighbor;
varweight=graph.AdjacentDistance(u,v);

if(distances[u]+weight<distances[v])
{
distances[v]=distances[u]+weight;
predecessors[v]=u;
}
}
}

privatevoidCheckForNegativeCycles()
{
foreach(varvertexingraph.Vertices)
{
if(vertex!=null)
{
CheckForNegativeCyclesForVertex(vertex);
}
}
}

privatevoidCheckForNegativeCyclesForVertex(Vertex<T>u)
{
foreach(varneighboringraph.GetNeighbors(u))
{
if(neighbor==null)
{
continue;
}

varv=neighbor;
varweight=graph.AdjacentDistance(u,v);

if(distances[u]+weight<distances[v])
{
thrownewInvalidOperationException("Graph contains a negative weight cycle.");
}
}
}
}