Исправить реализацию алгоритма Дейкстры - 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();
        }
    }
}

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


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

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

9   голосов , оценка 3.778 из 5
Похожие ответы