Кратчайший путь в графе: ошибка в программе - C#
Формулировка задачи:
Подскажите, пожалуйста, что не так? Программная реализация алгоритма Форда-Беллмана, поиск кратчайшего пути в графе
Листинг программы
- 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();
- }
- }
- }
Решение задачи: «Кратчайший путь в графе: ошибка в программе»
textual
Листинг программы
- 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++;
- }
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д