Алгоритм Дейкстры для большого количества точек - C#
Формулировка задачи:
Здравствуйте, реализовал программу для поиска кратчайшего пути по алгоритму Дикстры, но столкнулся с трудностью заполнения всех точек и ребер.
В вышеприведенном коде описаны 4 точки соединенные между собой в квадрат, а что делать если количество точек не 4, а например 100 или больше, не заполнять же руками все соединения.
Как должен выглядеть алгоритм для вышеприведенной таблицы если точки соединяются только со смежными, то есть 1 - 2, 2 - 3, и вниз 1 - 11, 11 - 21 и т.д
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]); }
Решение задачи: «Алгоритм Дейкстры для большого количества точек»
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)); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д