What could be a mistake? Does not consider the shortest way as it should

Graph with 3 vertices

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace FordBellman { class Ford { static void Main() { int n, s, m, k = 0, mod_e; // mod_e - Кол-во ребер (во всем графе) mod_e = k; // k - счетчик массивов ребер int[] a = new int[200]; // массив начал ребер int[] b = new int[200]; // массив концов ребер int[] w = new int[200]; // массив весов ребер int[] d = new int[200]; // массив расстояний Console.WriteLine("Введите количество вершин:"); n = int.Parse(Console.ReadLine()); // Количество вершин Console.WriteLine("\nВведите номер стартовой вершины:"); s = int.Parse(Console.ReadLine()); // Стартовая вершина for (int i = 1; i <= n; i++) // Задание массивов ребер { Console.WriteLine("\nВведите количество ребер, исходящих из вершины " +i); m = int.Parse(Console.ReadLine()); for (int j = 1; j <= m; j++) { a[k] = i; Console.WriteLine("\nВведите номер конечной вершины для "+ j + "-го ребра, исходящего из "+ i+ ":"); b[k] = int.Parse(Console.ReadLine()); Console.WriteLine("\nВведите вес "+ j+ "-го ребра, исходящего из "+ i+ ":"); w[k] = int.Parse(Console.ReadLine()); k++; } mod_e++; } for (int i = 1; i <= n; i++) d[i] = 999999; d[s] = 0; for (int i = 1; i < n; i++) { if (i == s) i++; else { for (int j = 1; j <= mod_e; j++) { if (d[b[j]] > (d[a[j]] + w[j])) d[b[j]] = d[a[j]] + w[j]; j++; } i++; } } for (int i = 1; i <= n; i++) { Console.WriteLine("\n\n\nКратчайший путь до вершины " + i + " = " + d[i]); } Console.WriteLine(d); Console.ReadLine(); } } }
  • if (i == s) i++; - Better do not change the iterator unnecessarily. If you need to skip a step, use the continue keyword. In your case, you could just do if (i != s) { ... } - MrModest

1 answer 1

This does not work because you increment j inside the j loop. Inside the loop, the variable of this loop is incremented by itself. And so you pass not through each vertex in the array and other arrays but through 1. And also when you write data into arrays of the type: w, a, etc., which are received by j then when writing you need to add one since other arrays were written with 1, and these, it turns out with 0. not - a[k] = i; a - a[k+1] = i; and with others as well.