Исправить реализацию алгоритма Дейкстры - C#
Формулировка задачи:
Подскажите пожалуйста новичку, как подставлять начальную и конечную точку графа, а точнее сделать их переменными , кто подскажет буду очень благодарен!
Листинг программы
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace ConsoleApplication1
- {
- class DekstraAlgorim
- {
- public Point[] points { get; private set; }
- public Rebro[] rebra { get; private set; }
- public Point BeginPoint { get; private set; }
- public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)
- {
- points = pointsOfgrath;
- rebra = rebraOfgrath;
- }
- /// <summary>
- /// Запуск алгоритма расчета
- /// </summary>
- /// <param name="beginp"></param>
- public void AlgoritmRun(Point beginp)
- {
- if (this.points.Count() == 0 || this.rebra.Count() == 0)
- {
- throw new DekstraException("Массив вершин или ребер не задан!");
- }
- else
- {
- BeginPoint = beginp;
- OneStep(beginp);
- foreach (Point point in points)
- {
- Point anotherP = GetAnotherUncheckedPoint();
- if (anotherP != null)
- {
- OneStep(anotherP);
- }
- else
- {
- break;
- }
- }
- }
- }
- /// <summary>
- /// Метод, делающий один шаг алгоритма. Принимает на вход вершину
- /// </summary>
- /// <param name="beginpoint"></param>
- public void OneStep(Point beginpoint)
- {
- foreach (Point nextp in Pred(beginpoint))
- {
- if (nextp.IsChecked == false)//не отмечена
- {
- float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
- if (nextp.ValueMetka > newmetka)
- {
- nextp.ValueMetka = newmetka;
- nextp.predPoint = beginpoint;
- }
- else
- {
- }
- }
- }
- beginpoint.IsChecked = true;//вычеркиваем
- }
- /// <summary>
- /// Поиск соседей для вершины. Для неориентированного графа ищутся все соседи.
- /// </summary>
- /// <param name="currpoint"></param>
- /// <returns></returns>
- private IEnumerable<Point> Pred(Point currpoint)
- {
- IEnumerable<Point> firstpoints = from ff in rebra where ff.FirstPoint == currpoint select ff.SecondPoint;
- IEnumerable<Point> secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
- IEnumerable<Point> totalpoints = firstpoints.Concat<Point>(secondpoints);
- return totalpoints;
- }
- /// <summary>
- /// Получаем ребро, соединяющее 2 входные точки
- /// </summary>
- /// <param name="a"></param>
- /// <param name="b"></param>
- /// <returns></returns>
- private Rebro GetMyRebro(Point a, Point b)
- {//ищем ребро по 2 точкам
- IEnumerable<Rebro> myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
- if (myr.Count() > 1 || myr.Count() == 0)
- {
- throw new DekstraException("Не найдено ребро между соседями!");
- }
- else
- {
- return myr.First();
- }
- }
- /// <summary>
- /// Получаем очередную неотмеченную вершину, "ближайшую" к заданной.
- /// </summary>
- /// <returns></returns>
- private Point GetAnotherUncheckedPoint()
- {
- IEnumerable<Point> pointsuncheck = from p in points where p.IsChecked == false select p;
- if (pointsuncheck.Count() != 0)
- {
- float minVal = pointsuncheck.First().ValueMetka;
- Point minPoint = pointsuncheck.First();
- foreach (Point p in pointsuncheck)
- {
- if (p.ValueMetka < minVal)
- {
- minVal = p.ValueMetka;
- minPoint = p;
- }
- }
- return minPoint;
- }
- else
- {
- return null;
- }
- }
- public List<Point> MinPath1(Point end)
- {
- List<Point> listOfpoints = new List<Point>();
- Point tempp = new Point();
- tempp = end;
- while (tempp != this.BeginPoint)
- {
- listOfpoints.Add(tempp);
- tempp = tempp.predPoint;
- }
- return listOfpoints;
- }
- }
- /// <summary>
- /// Класс, реализующий ребро
- /// </summary>
- class Rebro
- {
- public Point FirstPoint { get; private set; }
- public Point SecondPoint { get; private set; }
- public float Weight { get; private set; }
- public Rebro(Point first, Point second, float valueOfWeight)
- {
- FirstPoint = first;
- SecondPoint = second;
- Weight = valueOfWeight;
- }
- }
- /// <summary>
- /// Класс, реализующий вершину графа
- /// </summary>
- class Point
- {
- public float ValueMetka { get; set; }
- public string Name { get; private set; }
- public bool IsChecked { get; set; }
- public Point predPoint { get; set; }
- public object SomeObj { get; set; }
- public Point(int value, bool ischecked)
- {
- ValueMetka = value;
- IsChecked = ischecked;
- predPoint = new Point();
- }
- public Point(int value, bool ischecked, string name)
- {
- ValueMetka = value;
- IsChecked = ischecked;
- Name = name;
- predPoint = new Point();
- }
- public Point()
- {
- }
- }
- // <summary>
- /// для печати графа
- /// </summary>
- static class PrintGrath
- {
- public static List<string> PrintAllPoints(DekstraAlgorim da)
- {
- List<string> retListOfPoints = new List<string>();
- foreach (Point p in da.points)
- {
- retListOfPoints.Add(string.Format("point name={0}, point value={1}, predok={2}", p.Name, p.ValueMetka, p.predPoint.Name ?? "нет предка"));
- }
- return retListOfPoints;
- }
- public static List<string> PrintAllMinPaths(DekstraAlgorim da)
- {
- List<string> retListOfPointsAndPaths = new List<string>();
- foreach (Point p in da.points)
- {
- if (p != da.BeginPoint)
- {
- string s = string.Empty;
- foreach (Point p1 in da.MinPath1(p))
- {
- s += string.Format("{0} ", p1.Name);
- }
- retListOfPointsAndPaths.Add(string.Format("Point ={0},MinPath from {1} = {2}", p.Name, da.BeginPoint.Name, s));
- }
- }
- return retListOfPointsAndPaths;
- }
- }
- class DekstraException : ApplicationException
- {
- public DekstraException(string message)
- : base(message)
- {
- }
- }
- class Program
- {
- static void Main(string[] args)
- {
- Point[] v = new Point[6];
- v[0] = new Point(99999, false, "Chs");
- v[1] = new Point(99999, false, "Kv");
- v[2] = new Point(99999, false, "Chg");
- v[3] = new Point(99999, false, "Zht");
- v[4] = new Point(99999, false, "Pl");
- v[5] = new Point(99999, false, "Vn");
- Rebro[] rebras = new Rebro[9];
- rebras[0] = new Rebro(v[0], v[1], 190);//Chs-Kv
- rebras[1] = new Rebro(v[0], v[5], 343);//Chs-Vn
- rebras[2] = new Rebro(v[0], v[4], 279);//Chs-Pl
- rebras[3] = new Rebro(v[5], v[1], 256);//Vn-Kv
- rebras[4] = new Rebro(v[5], v[3], 125);//Vn-Zht
- rebras[5] = new Rebro(v[3], v[1], 131);//Zht-Kv
- rebras[6] = new Rebro(v[1], v[2], 149);//Kv-Chg
- rebras[7] = new Rebro(v[1], v[4], 337);//Kv-Pl
- rebras[8] = new Rebro(v[2], v[4], 477);//CHG-Pl
- DekstraAlgorim da = new DekstraAlgorim(v, rebras);
- da.AlgoritmRun(v[0]);
- List<string> b = PrintGrath.PrintAllMinPaths(da);
- for (int i = 0; i < b.Count; i++)
- Console.WriteLine(b[i]);
- Console.ReadKey(true);
- }
- }
- }
Решение задачи: «Исправить реализацию алгоритма Дейкстры»
textual
Листинг программы
- using System;
- using System.Collections.Generic;
- namespace Dijkstra
- {
- class Program
- {
- private static void Main()
- {
- const int n = 5;
- var adjacencyMatrix = new int[n, n];
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- adjacencyMatrix[i, j] = -1;
- }
- }
- adjacencyMatrix[0, 1] = 10;
- adjacencyMatrix[0, 3] = 30;
- adjacencyMatrix[0, 4] = 100;
- adjacencyMatrix[1, 2] = 50;
- adjacencyMatrix[2, 0] = 70;
- adjacencyMatrix[2, 4] = 10;
- adjacencyMatrix[3, 2] = 20;
- adjacencyMatrix[4, 3] = 60;
- var costs = new int[n];
- for (int i = 1; i < costs.Length; i++)
- {
- costs[i] = int.MaxValue;
- }
- for (int i = 0; i < n; i++)
- {
- var list = new List<int>();
- for (int j = i; j < n; j++)
- {
- if (adjacencyMatrix[i, j] != -1)
- list.Add(j);
- }
- list.Sort((x, y) => adjacencyMatrix[i, x].CompareTo(adjacencyMatrix[i, y])); //Сортируем по мин. стоимости пути
- foreach (var j in list)
- {
- var newcost = costs[i] + adjacencyMatrix[i, j];
- if (newcost < costs[j])
- costs[j] = newcost;
- }
- }
- for (int i = 0; i < costs.Length; i++)
- {
- Console.WriteLine("Пункт {0}, стоимость пути = {1}", i, costs[i]);
- }
- Console.ReadKey();
- }
- }
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д