Bellman-Ford Algorithm (shortest path from source)?

public class Edge {
public int Source, Dest, Weight;
public Edge(int s, int d, int w) {
Source = s; Dest = d; Weight = w;
}
}
int[] BellmanFord(int vertices, List<Edge> edges, int source) {
int[] dist = new int[vertices];
for (int i = 0; i < vertices; i++) dist[i] = int.MaxValue;
dist[source] = 0;

Follow on:

for (int i = 1; i < vertices; i++) {
foreach (var edge in edges) {
if (dist[edge.Source] != int.MaxValue &&

dist[edge.Source] + edge.Weight < dist[edge.Dest]) {

dist[edge.Dest] = dist[edge.Source] + edge.Weight;
}
}
}

// Detect negative weight cycle (optional)

foreach (var edge in edges) {
if (dist[edge.Source] != int.MaxValue && dist[edge.Source] +

edge.Weight < dist[edge.Dest]) {

throw new Exception("Graph contains negative weight

cycle");

}
}
return dist;
}

Explanation:

Relax edges V-1 times, then check for negative weight cycles.