Программа по нахождению кратчайшего пути (не могу прилепить нормальный вывод) - C#
Формулировка задачи:
Здравствуйте. Проблема заключается в следующем - программе не хватает вывода пути. Я никак не могу придумать, как сделать вывод. Подскажите как можно это реализовать?
PS консольное приложение
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication3 { class Program { static int i, j, n, p, xn, xk; static bool[] flag; static uint[,] c; static uint[] l; static int min(int n) { //поиск кратчайшего пути int i, result = 0; for (i = 0; i < n; i++) if (!(flag[i])) result = i; for (i = 0; i < n; i++) if ((l[result] > l[i]) && (!flag[i])) result = i; return result; } static uint minim(uint x, uint y) { if (x < y) return x; return y; } static void Main(string[] args) { string s = ""; bool z = false; string path = ""; Console.Write("Напишите число точек: "); //ввод количества вершин графа for (; ; ) { s = Console.ReadLine(); for (int q = 0; q < s.Length; q++) if (s[q] == '1' || s[q] == '2' || s[q] == '3' || s[q] == '4' || s[q] == '5' || s[q] == '6' || s[q] == '7' || s[q] == '8' || s[q] == '9' || s[q] == '0') { z = true; } else { z = false; break; } if (z == true) { n = Convert.ToInt32(s); break; } else Console.Write("Неверный ввод данных. Повторите, пожалуйста: "); } l = new uint[n]; c = new uint[n, n]; flag = new bool[n]; s = ""; //ввод длин рёбер for (i = 0; i < n; i++) for (j = 0; j < n; j++) c[i, j] = 0; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) { Console.Write(" задайте длину ребра x"); Console.Write(i + 1); Console.Write(" до x"); Console.Write(j + 1); Console.Write(": "); c[i, j] = Convert.ToUInt32(Console.ReadLine()); if (c[i, j] < 0) c[i, j] = 0; } Console.Write(" "); for (i = 0; i < n; i++) { Console.Write(" X"); Console.Write(i + 1); } Console.Write("\n"); Console.Write("\n"); //печать матрицы смежности for (i = 0; i < n; i++) { Console.Write("X{0:D}", i + 1); for (j = 0; j < n; j++) { Console.Write("{0,6:D}", c[i, j]); c[j, i] = c[i, j]; } Console.Write("\n\n"); } //избавление от нулей for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (c[i, j] == 0) c[i, j] = 65535; //ввод начальной точки пути Console.Write(" задайте начальную точку: "); xn = Convert.ToInt32(Console.ReadLine()); path = Convert.ToString(xn + " "); //ввод конечной точки пути Console.Write(" задайте конечную точку: "); xk = Convert.ToInt32(Console.ReadLine()); int rem = xk; xk--; xn--; //проверка на совпадение точек if (xn == xk) { Console.WriteLine("Начальная и конечные точки совпадают"); Console.ReadLine(); return; } for (i = 0; i < n; i++) { flag[i] = false; l[i] = 65535; } //установка начальной точки l[xn] = 0; flag[xn] = true; p = xn; s = Convert.ToString(xn + 1); //расчёт путей и выбор кратчайшего пути do { for (i = 0; i < n; i++) if ((c[p, i] != 65535) && (!flag[i]) && (i != p)) { if (l[i] > l[p] + c[p, i]) { s = Convert.ToString(i + 1); } l[i] = minim(l[i], l[p] + c[p, i]); } p = min(n); //запись пути path += (p+1) + " "; flag[p] = true; } while (p != xk); //вывод полученных данных if (l[p] < 65535) { Console.Write("Put: "); Console.Write(path); Console.Write("\n"); Console.Write("Dlina puti: "); Console.Write(l[p]); Console.Write("\n"); } else Console.Write("Путь не существует!"); Console.Write("\n"); Console.ReadLine(); } } }
Решение задачи: «Программа по нахождению кратчайшего пути (не могу прилепить нормальный вывод)»
textual
Листинг программы
Console.Write(path);
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д