Здравствуйте, Жуковцы, реализовал программу для поиска кратчайшего пути по алгоритму Дикстры, но столкнулся с трудностью заполнения всех точек и ребер.
В вышеприведенном коде описаны 4 точки соединенные между собой в квадрат, а что делать если количество точек не 4, а например 100 или больше, не заполнять же руками все соединения.
[Ссылки могут видеть только зарегистрированные пользователи. ]
Как должен выглядеть алгоритм для вышеприведенной таблицы если точки соединяются только со смежными, то есть 1 - 2, 2 - 3, и вниз 1 - 11, 11 - 21 и т.д
Добавлено через 2 минуты
Можно еще по диагонали и в обратном порядке
________________
Talk is cheap. Show me the code
— Linus Torvalds
Последний раз редактировалось Yukikaze; 03.02.2012 в 22:20.
Причина: Добавлено сообщение
Re: Алгоритм Дикстры для большого количества точек
В графах я, говорю откровенно - не разбираюсь, но помоему обычно графы представляют в виде двумерной матрицы..
1|2|3|4
1*|*|*|*
2*|*|*|*
3*|*|*|*
4*|*|*|*
Где * - расстояние между точками.
Если бинарная связь между ними отсутствует вместо расстояния, очевидно - null.
На хабре была неплохая статейка по этому методу, думаю есть смысл глянуть.
Кстати, если я не ошибаюсь, произносится "Дейкстра" а не "Дикстра".
________________
Ну что лежишь ты Мурка, на краю дороги
Гробоваая крыышкаа над тобооой
Re: Алгоритм Дикстры для большого количества точек
Все, мы перестали друг друга понимать, мне всего лишь надо разбить массив с картинки на фрагменты типа
0 -1, 1 - 2, 2 - 3, 3 -4, 4 -5, 5 -6, 6 - 7, 7 - 8, 8 - 9
0 - 10, 10 - 20, 20 - 30
ну и так далее, просто я когда понял, что надо заполнить все соединения в сетке 1000х1000 я... ну вы поняли, да?
Re: Алгоритм Дикстры для большого количества точек
Цитата:
Сообщение от Yukikaze
Все, мы перестали друг друга понимать, мне всего лишь надо разбить массив с картинки на фрагменты типа
0 -1, 1 - 2, 2 - 3, 3 -4, 4 -5, 5 -6, 6 - 7, 7 - 8, 8 - 9
0 - 10, 10 - 20, 20 - 30
ну и так далее, просто я когда понял, что надо заполнить все соединения в сетке 1000х1000 я... ну вы поняли, да?
Re: Алгоритм Дикстры для большого количества точек
Код:
myStruct {int start,int end,int lenght}; // структура ребра
list<myStruct> m = new List<myStruct>; // здесь я храню все ребра
int lastElem = 100; //размер таблицы
for(int i = 0 , i< lastElem, i++)
{
if( i % Math.Sqrt(maxElem) == 0 ) //
{
int a = Math.Sqrt(maxElem); // получаем к-во елементов в строчке
if( i == 0) // просто исключительный случай когда это 1й елемент
{
m.Add(i,i + a, 0);//снизу
m.Add(i,i + a +1, 0); // снизу и справа
m.Add(i,i + 1, 0);// справа
continue; // переходим на след. итерацию.
}
if( i < a-1 ) // елемент из 1й строчки
{
m.Add(i,i+a, 0);//снизу
m.Add(i,i+a+1, 0); // снизу и справа
m.Add(i,i+1, 0);// справа
m.Add(i,i - 1, 0);// слева
m.Add(i,i + a-1, 0);// внизу и слева
continue;
}
if ( maxElem - i < a) // если последний елемент левого столбца
{
m.Add(i, i-a, 0);// сверху
m.Add(i, i-a-1, 0); // сверху и справа
m.Add(i, i+1, 0);// справа
}
else // елемент 1го столбца
{
m.Add(i, i-a, 0);// сверху
m.Add(i, i-9, 0); // сверху и справа
m.Add(i, i+a, 0);//снизу
m.Add(i, i+a+1, 0); // снизу и справа
m.Add(i, i+1, 0);// справа
continue;
}
}
if( i % a == a-1 ) // правый ряд
{
if( i == lastElem-1 ) // последний
{
m.Add(i, i - a, 0);// сверху
m.Add(i, i -a-1 , 0);// сверху и слева
m.Add(i,i - 1, 0);// слева
continue;
}
if ( i == Math.Sqrt(maxElem)-1 ) // 1й в столбце
{
m.Add(i, i + a, 0);// снизу
m.Add(i, i + a-1 , 0);// снизу и слева
m.Add(i,i - 1, 0);// слева
continue;
}
else
{
m.Add(i, i - a, 0);// сверху
m.Add(i, i - a-1 , 0);// сверху и слева
m.Add(i,i - 1, 0);// слева
m.Add(i, i + a, 0);// снизу
m.Add(i, i + a-1 , 0);// снизу и слева
continue;
}
}
if( i/a == a-1 ) // нижний ряд минус крайние елементы
{
m.Add(i, i - a, 0);// сверху
m.Add(i, i - a-1 , 0);// сверху и слева
m.Add(i, i- a+1, 0); // сверху и справа
m.Add(i, i - 1, 0);// левый
m.Add(i, i + 1 , 0);// правый
}
else // все центральные елементы
{
m.Add(i, i - a, 0);// сверху
m.Add(i, i - a-1 , 0);// сверху и слева
m.Add(i, i-a+1, 0); // сверху и справа
m.Add(i, i - 1, 0);// левый
m.Add(i, i + 1 , 0);// правый
m,Add(i, i + a , 0); // снизу
m,Add(i, i+ a-1 , 0); // снизу и слева
m,Add(i, i + a+1 , 0); // снизу и справа
}
}
извини, код с коленки... но вроде все ситуации рассмотрел...
PS: знаю что писец.
Добавлено через 29 минут
Цитата:
Сообщение от Sinyss
int a = Math.Sqrt(maxElem); // получаем к-во елементов в строчке
Оу, сори это сразу перед первым if
Последний раз редактировалось Sinyss; 04.02.2012 в 00:08.
Причина: Добавлено сообщение
вот здесь.
У меня размер матрицы задается размером массива, короче полный код выглядит вот так:
Код:
void doIt(int Size)
{
re = new RouteEngine.RouteEngine();
int[] arr0 = new int[Size];
int[] arr10 = new int[Size];
for (int i = 0; i < arr0.Length; i++)
{
arr0[i] = i;
arr10[i] = i*10;
}
var allLocations = new List<Location>();
List<Connection> allConection = new List<Connection>();
for (int i = 0; i < 100; i++ )
{
allLocations.Add(new Location{Identifier = i.ToString()});
}
foreach (Location _loc in allLocations)
{
re.Locations.Add(_loc);
}
//Вниз
foreach (int i in arr10)
{
foreach (int n in arr0)
{
if (i + n != 9 && (i + n + 1) % 10 != 0)
allConection.Add(new Connection(allLocations[i + n],allLocations[i + n + 1], 4)); // (i + n) + " " + ((i + n) + 1));
}
}
//Вверх
foreach (int i in arr10)
{
foreach (int n in arr0)
{
if (i + n != 9 && (i + n + 1) % 10 != 0)
allConection.Add(new Connection(allLocations[i + n + 1], allLocations[i + n], 4)); // (i + n) + " " + ((i + n) + 1));
}
}
//Вправо
foreach (int i in arr0)
{
foreach (int n in arr10)
{
if ((i + n - 10) >= 0)
allConection.Add(new Connection(allLocations[i + n - 10], allLocations[i + n], 4)); //listBox1.Items.Add((i + n - 10) + " " + (i + n));
}
}
//Влево
foreach (int i in arr0)
{
foreach (int n in arr10)
{
if ((i + n - 10) >= 0)
allConection.Add(new Connection(allLocations[i + n], allLocations[i + n - 10], 4)); //listBox1.Items.Add((i + n - 10) + " " + (i + n));
}
}
re.Connections.AddRange(allConection);
Dictionary<Location, Route> _shortestPaths = re.CalculateMinCost(allLocations[0]);
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]);
}
}
PS Нужен алгоритм соединения по диагонали, ибо этот "ход конем" меня задолбал, из 0 до 99 идет по периметру за 19 ходов, вместо 10 по диагонали
Добавлено через 1 час 29 минут
Вручайте, где может быть ошибка если соединяет 0 и 9, 10 и 19, 90 и 99 и т.д.
Появляется при добавлении диагонали
Код:
//Диагональ 1
foreach (int i in arr10)
{
foreach (int n in arr0)
{
if (i + n <= 99)
allConection.Add(new Connection(allLocations[i], allLocations[i + n], 5));
}
}
________________
Talk is cheap. Show me the code
— Linus Torvalds
Последний раз редактировалось Yukikaze; 04.02.2012 в 03:40.
Причина: Добавлено сообщение
Регистрация: 01.10.2011
Сообщений: 128
Популярность: 5723
Сказал(а) спасибо: 25
Алгоритм Дикстры для большого количества точек
