Исправить реализацию алгоритма Дейкстры - C#

Узнай цену своей работы

Формулировка задачи:

Подскажите пожалуйста новичку, как подставлять начальную и конечную точку графа, а точнее сделать их переменными , кто подскажет буду очень благодарен!
Листинг программы
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. namespace ConsoleApplication1
  7. {
  8. class DekstraAlgorim
  9. {
  10. public Point[] points { get; private set; }
  11. public Rebro[] rebra { get; private set; }
  12. public Point BeginPoint { get; private set; }
  13. public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)
  14. {
  15. points = pointsOfgrath;
  16. rebra = rebraOfgrath;
  17. }
  18. /// <summary>
  19. /// Запуск алгоритма расчета
  20. /// </summary>
  21. /// <param name="beginp"></param>
  22. public void AlgoritmRun(Point beginp)
  23. {
  24. if (this.points.Count() == 0 || this.rebra.Count() == 0)
  25. {
  26. throw new DekstraException("Массив вершин или ребер не задан!");
  27. }
  28. else
  29. {
  30. BeginPoint = beginp;
  31. OneStep(beginp);
  32. foreach (Point point in points)
  33. {
  34. Point anotherP = GetAnotherUncheckedPoint();
  35. if (anotherP != null)
  36. {
  37. OneStep(anotherP);
  38. }
  39. else
  40. {
  41. break;
  42. }
  43. }
  44. }
  45. }
  46. /// <summary>
  47. /// Метод, делающий один шаг алгоритма. Принимает на вход вершину
  48. /// </summary>
  49. /// <param name="beginpoint"></param>
  50. public void OneStep(Point beginpoint)
  51. {
  52. foreach (Point nextp in Pred(beginpoint))
  53. {
  54. if (nextp.IsChecked == false)//не отмечена
  55. {
  56. float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
  57. if (nextp.ValueMetka > newmetka)
  58. {
  59. nextp.ValueMetka = newmetka;
  60. nextp.predPoint = beginpoint;
  61. }
  62. else
  63. {
  64. }
  65. }
  66. }
  67. beginpoint.IsChecked = true;//вычеркиваем
  68. }
  69. /// <summary>
  70. /// Поиск соседей для вершины. Для неориентированного графа ищутся все соседи.
  71. /// </summary>
  72. /// <param name="currpoint"></param>
  73. /// <returns></returns>
  74. private IEnumerable<Point> Pred(Point currpoint)
  75. {
  76. IEnumerable<Point> firstpoints = from ff in rebra where ff.FirstPoint == currpoint select ff.SecondPoint;
  77. IEnumerable<Point> secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
  78. IEnumerable<Point> totalpoints = firstpoints.Concat<Point>(secondpoints);
  79. return totalpoints;
  80. }
  81. /// <summary>
  82. /// Получаем ребро, соединяющее 2 входные точки
  83. /// </summary>
  84. /// <param name="a"></param>
  85. /// <param name="b"></param>
  86. /// <returns></returns>
  87. private Rebro GetMyRebro(Point a, Point b)
  88. {//ищем ребро по 2 точкам
  89. IEnumerable<Rebro> myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
  90. if (myr.Count() > 1 || myr.Count() == 0)
  91. {
  92. throw new DekstraException("Не найдено ребро между соседями!");
  93. }
  94. else
  95. {
  96. return myr.First();
  97. }
  98. }
  99. /// <summary>
  100. /// Получаем очередную неотмеченную вершину, "ближайшую" к заданной.
  101. /// </summary>
  102. /// <returns></returns>
  103. private Point GetAnotherUncheckedPoint()
  104. {
  105. IEnumerable<Point> pointsuncheck = from p in points where p.IsChecked == false select p;
  106. if (pointsuncheck.Count() != 0)
  107. {
  108. float minVal = pointsuncheck.First().ValueMetka;
  109. Point minPoint = pointsuncheck.First();
  110. foreach (Point p in pointsuncheck)
  111. {
  112. if (p.ValueMetka < minVal)
  113. {
  114. minVal = p.ValueMetka;
  115. minPoint = p;
  116. }
  117. }
  118. return minPoint;
  119. }
  120. else
  121. {
  122. return null;
  123. }
  124. }
  125. public List<Point> MinPath1(Point end)
  126. {
  127. List<Point> listOfpoints = new List<Point>();
  128. Point tempp = new Point();
  129. tempp = end;
  130. while (tempp != this.BeginPoint)
  131. {
  132. listOfpoints.Add(tempp);
  133. tempp = tempp.predPoint;
  134. }
  135. return listOfpoints;
  136. }
  137. }
  138. /// <summary>
  139. /// Класс, реализующий ребро
  140. /// </summary>
  141. class Rebro
  142. {
  143. public Point FirstPoint { get; private set; }
  144. public Point SecondPoint { get; private set; }
  145. public float Weight { get; private set; }
  146. public Rebro(Point first, Point second, float valueOfWeight)
  147. {
  148. FirstPoint = first;
  149. SecondPoint = second;
  150. Weight = valueOfWeight;
  151. }
  152. }
  153. /// <summary>
  154. /// Класс, реализующий вершину графа
  155. /// </summary>
  156. class Point
  157. {
  158. public float ValueMetka { get; set; }
  159. public string Name { get; private set; }
  160. public bool IsChecked { get; set; }
  161. public Point predPoint { get; set; }
  162. public object SomeObj { get; set; }
  163. public Point(int value, bool ischecked)
  164. {
  165. ValueMetka = value;
  166. IsChecked = ischecked;
  167. predPoint = new Point();
  168. }
  169. public Point(int value, bool ischecked, string name)
  170. {
  171. ValueMetka = value;
  172. IsChecked = ischecked;
  173. Name = name;
  174. predPoint = new Point();
  175. }
  176. public Point()
  177. {
  178. }
  179. }
  180. // <summary>
  181. /// для печати графа
  182. /// </summary>
  183. static class PrintGrath
  184. {
  185. public static List<string> PrintAllPoints(DekstraAlgorim da)
  186. {
  187. List<string> retListOfPoints = new List<string>();
  188. foreach (Point p in da.points)
  189. {
  190. retListOfPoints.Add(string.Format("point name={0}, point value={1}, predok={2}", p.Name, p.ValueMetka, p.predPoint.Name ?? "нет предка"));
  191. }
  192. return retListOfPoints;
  193. }
  194. public static List<string> PrintAllMinPaths(DekstraAlgorim da)
  195. {
  196. List<string> retListOfPointsAndPaths = new List<string>();
  197. foreach (Point p in da.points)
  198. {
  199. if (p != da.BeginPoint)
  200. {
  201. string s = string.Empty;
  202. foreach (Point p1 in da.MinPath1(p))
  203. {
  204. s += string.Format("{0} ", p1.Name);
  205. }
  206. retListOfPointsAndPaths.Add(string.Format("Point ={0},MinPath from {1} = {2}", p.Name, da.BeginPoint.Name, s));
  207. }
  208. }
  209. return retListOfPointsAndPaths;
  210. }
  211. }
  212. class DekstraException : ApplicationException
  213. {
  214. public DekstraException(string message)
  215. : base(message)
  216. {
  217. }
  218. }
  219. class Program
  220. {
  221. static void Main(string[] args)
  222. {
  223. Point[] v = new Point[6];
  224. v[0] = new Point(99999, false, "Chs");
  225. v[1] = new Point(99999, false, "Kv");
  226. v[2] = new Point(99999, false, "Chg");
  227. v[3] = new Point(99999, false, "Zht");
  228. v[4] = new Point(99999, false, "Pl");
  229. v[5] = new Point(99999, false, "Vn");
  230. Rebro[] rebras = new Rebro[9];
  231. rebras[0] = new Rebro(v[0], v[1], 190);//Chs-Kv
  232. rebras[1] = new Rebro(v[0], v[5], 343);//Chs-Vn
  233. rebras[2] = new Rebro(v[0], v[4], 279);//Chs-Pl
  234. rebras[3] = new Rebro(v[5], v[1], 256);//Vn-Kv
  235. rebras[4] = new Rebro(v[5], v[3], 125);//Vn-Zht
  236. rebras[5] = new Rebro(v[3], v[1], 131);//Zht-Kv
  237. rebras[6] = new Rebro(v[1], v[2], 149);//Kv-Chg
  238. rebras[7] = new Rebro(v[1], v[4], 337);//Kv-Pl
  239. rebras[8] = new Rebro(v[2], v[4], 477);//CHG-Pl
  240. DekstraAlgorim da = new DekstraAlgorim(v, rebras);
  241. da.AlgoritmRun(v[0]);
  242. List<string> b = PrintGrath.PrintAllMinPaths(da);
  243. for (int i = 0; i < b.Count; i++)
  244. Console.WriteLine(b[i]);
  245. Console.ReadKey(true);
  246. }
  247. }
  248. }

Решение задачи: «Исправить реализацию алгоритма Дейкстры»

textual
Листинг программы
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace Dijkstra
  5. {
  6.     class Program
  7.     {
  8.         private static void Main()
  9.         {
  10.  
  11.             const int n = 5;
  12.             var adjacencyMatrix = new int[n, n];
  13.             for (int i = 0; i < n; i++)
  14.             {
  15.                 for (int j = 0; j < n; j++)
  16.                 {
  17.                     adjacencyMatrix[i, j] = -1;
  18.                 }
  19.             }
  20.             adjacencyMatrix[0, 1] = 10;
  21.             adjacencyMatrix[0, 3] = 30;
  22.             adjacencyMatrix[0, 4] = 100;
  23.             adjacencyMatrix[1, 2] = 50;
  24.             adjacencyMatrix[2, 0] = 70;
  25.             adjacencyMatrix[2, 4] = 10;
  26.             adjacencyMatrix[3, 2] = 20;
  27.             adjacencyMatrix[4, 3] = 60;
  28.  
  29.             var costs = new int[n];
  30.             for (int i = 1; i < costs.Length; i++)
  31.             {
  32.                 costs[i] = int.MaxValue;
  33.             }
  34.  
  35.             for (int i = 0; i < n; i++)
  36.             {
  37.                 var list = new List<int>();
  38.                 for (int j = i; j < n; j++)
  39.                 {
  40.                     if (adjacencyMatrix[i, j] != -1)
  41.                         list.Add(j);
  42.                 }
  43.                 list.Sort((x, y) => adjacencyMatrix[i, x].CompareTo(adjacencyMatrix[i, y])); //Сортируем по мин. стоимости пути
  44.                 foreach (var j in list)
  45.                 {
  46.                     var newcost = costs[i] + adjacencyMatrix[i, j];
  47.                     if (newcost < costs[j])
  48.                         costs[j] = newcost;
  49.                 }
  50.             }
  51.             for (int i = 0; i < costs.Length; i++)
  52.             {
  53.                 Console.WriteLine("Пункт {0}, стоимость пути = {1}", i, costs[i]);
  54.             }
  55.             Console.ReadKey();
  56.         }
  57.     }
  58. }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.778 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы