Bellman-Ford, negative weight search

The Bellman-Ford algorithm is used to find the shortest path in a graph, which may have negative weight edges. It is slower than Dijkstra's algorithm but can handle graphs with negative weights.

public static void BellmanFordAlgorithm(Dictionary<string, Dictionary<string, int>> graph, string start, string end)
{
    Dictionary<string, int> distance = new Dictionary<string, int>();
    Dictionary<string, string> predecessor = new Dictionary<string, string>();

    foreach (var node in graph.Keys)
    {
        distance[node] = int.MaxValue;
        predecessor[node] = null;
    }

    distance[start] = 0;

    for (int i = 0; i < graph.Keys.Count - 1; i++)
    {
        foreach (var node in graph.Keys)
        {
            foreach (var edge in graph[node])
            {
                string neighborNode = edge.Key;
                int edgeDistance = edge.Value;

                if (distance[node] != int.MaxValue && distance[node] + edgeDistance < distance[neighborNode])
                {
                    distance[neighborNode] = distance[node] + edgeDistance;
                    predecessor[neighborNode] = node;
                }
            }
        }
    }

    foreach (var node in graph.Keys)
    {
        foreach (var edge in graph[node])
        {
            string neighborNode = edge.Key;
            int edgeDistance = edge.Value;

            if (distance[node] != int.MaxValue && distance[node] + edgeDistance < distance[neighborNode])
            {
                Console.WriteLine("Graph contains a negative-weight cycle");
                return;
            }
        }
    }

    var path = new List<string>();
    for (var node = end; node != null; node = predecessor[node])
    {
        path.Add(node);
    }

    path.Reverse();

    Console.WriteLine(
        $"Shortest path from {start} to {end}: {string.Join(" -> ", path)} with a total distance of {distance[end]}.");
}

Use it like this:

var graph = new Dictionary<string, Dictionary<string, int>>();
graph["A"] = new Dictionary<string, int> { { "B", 5 }, { "C", 2 } };
graph["B"] = new Dictionary<string, int> { { "D", 1 } };
graph["C"] = new Dictionary<string, int> { { "B", -2 } };
graph["D"] = new Dictionary<string, int> { };

PrintOuts.BellmanFordAlgorithm(graph, "A", "D");

Shortest path from A to D: A -> C -> B -> D with a total distance of 1.

Based on the given graph and the Bellman-Ford algorithm, it goes through the path A -> C -> B -> D with total cost 1, instead of A -> B -> D with total cost 6, even though there's a negative weight on the path, showing that the algorithm successfully identifies and handles negative weights correctly.

No files yet, migration hasn't completed yet!