C# Coding Test Course, Bellman-Ford

As you often solve algorithm problems, you will encounter various shortest path problems. Among them, the “Bellman-Ford algorithm” is a useful algorithm for finding the shortest path in a graph that includes edges with negative weights. In this lecture, we will gain a deep understanding of the Bellman-Ford algorithm and solve a problem using it.

Introduction to the Bellman-Ford Algorithm

The Bellman-Ford algorithm is an algorithm for finding the shortest path from the starting point to all vertices in a given graph. This algorithm has the following characteristics:

  • It can find the shortest path even in graphs with edges that have negative weights.
  • If a negative cycle exists, the shortest path cannot be defined.
  • The time complexity is O(VE), where V is the number of vertices and E is the number of edges.

How the Bellman-Ford Algorithm Works

This algorithm works as follows:

  1. Initialize the distance values of all vertices to infinity. However, set the distance value of the starting vertex to 0.
  2. For all edges, update the distance value if it can be moved through that edge.
  3. Repeat this process V – 1 times because the longest path can consist of V – 1 edges.
  4. Finally, check once more for all edges to see if a negative cycle exists.

Problem Description

Problem: Finding the Shortest Path

Given the number of vertices N and edges M in a graph, find the shortest path from the starting vertex S to all other vertices. There may be edges with negative weights, and if a negative cycle exists, print “Negative Cycle”.

Input
3 3 1
1 2 2
1 3 3
2 3 -5

Output
1 0 2

Explanation of the Input Example

The above input example represents the following graph:

Number of vertices: 3

Number of edges: 3

Starting vertex: 1

  • 1 ↔ 2 : Weight 2
  • 1 ↔ 3 : Weight 3
  • 2 ↔ 3 : Weight -5

Code Implementation

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Input
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]); // Number of vertices
        int M = int.Parse(input[1]); // Number of edges
        int S = int.Parse(input[2]); // Starting vertex

        // Initialize graph
        List> edges = new List>();
        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            int u = int.Parse(input[0]); // Starting vertex
            int v = int.Parse(input[1]); // Destination vertex
            int w = int.Parse(input[2]); // Weight
            edges.Add(Tuple.Create(u, v, w));
        }

        // Initialize distance array
        int[] distance = new int[N + 1];
        Array.Fill(distance, int.MaxValue);
        distance[S] = 0;

        // Bellman-Ford algorithm
        for (int i = 1; i <= N - 1; i++)
        {
            foreach (var edge in edges)
            {
                int u = edge.Item1;
                int v = edge.Item2;
                int w = edge.Item3;
                if (distance[u] != int.MaxValue && distance[u] + w < distance[v])
                {
                    distance[v] = distance[u] + w;
                }
            }
        }

        // Check for negative cycle
        bool hasNegativeCycle = false;
        foreach (var edge in edges)
        {
            int u = edge.Item1;
            int v = edge.Item2;
            int w = edge.Item3;
            if (distance[u] != int.MaxValue && distance[u] + w < distance[v])
            {
                hasNegativeCycle = true;
                break;
            }
        }

        // Output result
        if (hasNegativeCycle)
        {
            Console.WriteLine("Negative Cycle");
        }
        else
        {
            for (int i = 1; i <= N; i++)
            {
                Console.WriteLine(distance[i] == int.MaxValue ? "INF" : distance[i].ToString());
            }
        }
    }
}

Code Explanation

The above code implements the Bellman-Ford algorithm. Let me explain the main parts of the code.

  • List<Tuple<int, int, int>> edges: A list to store edge information.
  • int[] distance: Stores the shortest distance to each vertex. The initial value is set to infinity, and the starting vertex's distance is initialized to 0.
  • In the core loop of the Bellman-Ford algorithm, distances are updated by checking each edge.
  • At the end, edges are checked once more to verify if a negative cycle exists.

Conclusion

In this lecture, we examined the concept of the Bellman-Ford algorithm and the process of solving a problem using it. By deeply understanding the principles of the algorithm and implementing it in code, you can enhance your ability to apply it in coding tests.

The Bellman-Ford algorithm is also used in various practical shortest path problems, so be sure to understand it thoroughly and practice to prepare for coding tests.