Алгоритм Дейкстры для большого количества точек - C#

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

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

Здравствуйте, реализовал программу для поиска кратчайшего пути по алгоритму Дикстры, но столкнулся с трудностью заполнения всех точек и ребер.
re = new RouteEngine.RouteEngine();
            Location loc0 = new Location { Identifier = "leftBot" };
            Location loc1 = new Location { Identifier = "leftTop" };
            Location loc2 = new Location { Identifier = "rightTop" };
            Location loc3 = new Location { Identifier = "rightBot" };
 
            re.Locations.Add(loc0);
            re.Locations.Add(loc1);
            re.Locations.Add(loc2);
            re.Locations.Add(loc3);
 
            re.Connections.Add(new Connection(loc0, loc1, 4));
            re.Connections.Add(new Connection(loc1, loc2, 4));
            re.Connections.Add(new Connection(loc2, loc3, 4));
            re.Connections.Add(new Connection(loc3, loc0, 4));
            re.Connections.Add(new Connection(loc1, loc0, 4));
            re.Connections.Add(new Connection(loc2, loc1, 4));
            re.Connections.Add(new Connection(loc3, loc2, 4));
            re.Connections.Add(new Connection(loc0, loc3, 4));
 
            Dictionary<Location, Route> _shortestPaths = re.CalculateMinCost(loc0);
            var _shortestLocations = (List<Location>)(from s in _shortestPaths orderby s.Value.Cost select s.Key).ToList();
            
            foreach (var _location in _shortestLocations)
            {
                listBox1.Items.Add(_shortestPaths[_location]);
            }
В вышеприведенном коде описаны 4 точки соединенные между собой в квадрат, а что делать если количество точек не 4, а например 100 или больше, не заполнять же руками все соединения. Как должен выглядеть алгоритм для вышеприведенной таблицы если точки соединяются только со смежными, то есть 1 - 2, 2 - 3, и вниз 1 - 11, 11 - 21 и т.д

Решение задачи: «Алгоритм Дейкстры для большого количества точек»

textual
Листинг программы
int size = (int)Math.Sqrt(allLocations.Count);
int last = size - 1; // Последний элемент
for (int i = 0; i < size - 1; i++)
{
    // Диагональ с верхнего левого в нижний правый угол
    //Console.WriteLine("{0} {1}", i * size + i, (i + 1) * size + i + 1);
    allConection.Add(new Connection(allLocations[i * size + i], allLocations[(i + 1) * size + i + 1], 4));
    // Диагональ с верхнего правого в нижний левый угол
    //Console.WriteLine("{0} {1}", i * size + last - i, (i + 1) * size + last - (i + 1));
    allConection.Add(new Connection(allLocations[i * size + last - i], allLocations[(i + 1) * size + last - (i + 1)], 4));
}

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


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

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

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