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.