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.<\/p>\n
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:<\/p>\n
This algorithm works as follows:<\/p>\n
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”.<\/p>\n
Input\n3 3 1\n1 2 2\n1 3 3\n2 3 -5\n\nOutput\n1 0 2\n<\/code><\/pre>\nExplanation of the Input Example<\/h3>\n
The above input example represents the following graph:<\/p>\n
Number of vertices: 3<\/p>\n
Number of edges: 3<\/p>\n
Starting vertex: 1<\/p>\n
\n- 1 \u2194 2 : Weight 2<\/li>\n
- 1 \u2194 3 : Weight 3<\/li>\n
- 2 \u2194 3 : Weight -5<\/li>\n<\/ul>\n
Code Implementation<\/h2>\nusing System;\nusing System.Collections.Generic;\n\nclass Program\n{\n static void Main()\n {\n \/\/ Input\n string[] input = Console.ReadLine().Split();\n int N = int.Parse(input[0]); \/\/ Number of vertices\n int M = int.Parse(input[1]); \/\/ Number of edges\n int S = int.Parse(input[2]); \/\/ Starting vertex\n\n \/\/ Initialize graph\n List> edges = new List>();\n for (int i = 0; i < M; i++)\n {\n input = Console.ReadLine().Split();\n int u = int.Parse(input[0]); \/\/ Starting vertex\n int v = int.Parse(input[1]); \/\/ Destination vertex\n int w = int.Parse(input[2]); \/\/ Weight\n edges.Add(Tuple.Create(u, v, w));\n }\n\n \/\/ Initialize distance array\n int[] distance = new int[N + 1];\n Array.Fill(distance, int.MaxValue);\n distance[S] = 0;\n\n \/\/ Bellman-Ford algorithm\n for (int i = 1; i <= N - 1; i++)\n {\n foreach (var edge in edges)\n {\n int u = edge.Item1;\n int v = edge.Item2;\n int w = edge.Item3;\n if (distance[u] != int.MaxValue && distance[u] + w < distance[v])\n {\n distance[v] = distance[u] + w;\n }\n }\n }\n\n \/\/ Check for negative cycle\n bool hasNegativeCycle = false;\n foreach (var edge in edges)\n {\n int u = edge.Item1;\n int v = edge.Item2;\n int w = edge.Item3;\n if (distance[u] != int.MaxValue && distance[u] + w < distance[v])\n {\n hasNegativeCycle = true;\n break;\n }\n }\n\n \/\/ Output result\n if (hasNegativeCycle)\n {\n Console.WriteLine(\"Negative Cycle\");\n }\n else\n {\n for (int i = 1; i <= N; i++)\n {\n Console.WriteLine(distance[i] == int.MaxValue ? \"INF\" : distance[i].ToString());\n }\n }\n }\n}\n<\/code><\/pre>\nCode Explanation<\/h3>\n
The above code implements the Bellman-Ford algorithm. Let me explain the main parts of the code.<\/p>\n
\nList<Tuple<int, int, int>> edges<\/code>: A list to store edge information.<\/li>\nint[] distance<\/code>: Stores the shortest distance to each vertex. The initial value is set to infinity, and the starting vertex's distance is initialized to 0.<\/li>\n- In the core loop of the Bellman-Ford algorithm, distances are updated by checking each edge.<\/li>\n
- At the end, edges are checked once more to verify if a negative cycle exists.<\/li>\n<\/ul>\n
Conclusion<\/h2>\n
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.<\/p>\n
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.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"