Исправить реализацию алгоритма Дейкстры - 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(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д