Приветствую Вас, 01010101! Простенькая реализация алгоритма Деикстры(нахождение кратчайшего расстояния между двумя узлами графа) nNodes-количество узлов matrAdjacent-матрица смежности (задает пути между узлами), может быть использована для любого типа графа matrShortrestPath-матрица кратчайших путей, одномерный массив nNodes*nNodes, представляющий собой в начале поиска копию матрицы смежности Собственно алгоритм реализован в функции loadShortresPath() На каждой стадии алгоритм выбирает узел, содержащий наименьшее расстояние, и объявляет его кратчайшим. Функция loadAdjacentMatr() была, в свое время написана, как небольшое издевательство над преподавателем (попробуй загрузить матрицу хотя бы 6х6) так, что ее лучше переписать. Ну а получить кратчайшее расстояние - вызов findShortestPath(начало,конец), вычисляется оно еще в конструкторе.
Приложение: Ответ отправлен: 15.06.2004, 23:05 Отправитель: bocha
Вопрос № 1711
К вопросу про нахождение кратчайшего пути. Эксперты меня не правильно поняли. Есть двухмерная-матрица matr(M,N): 111111111111 1!01001000001 101010101001 1000100010^1 111111111111 Надо от точки A(!) найти кратчайший путь до B(^). Как это сделать
Приветствую Вас, MATRIZA! Если бы вы сказали каким образом осуществляется перемещение по элементам матрицы, я бы помог. Я так понял что надо например по единичкам пройти от т.А до т.B ? Т.е. типа так: 111111111111 *!01001000001 *01010101001 *000100010^1 ***********1 (звездочками обозначил путь) или нет? Ответ отправлен: 16.06.2004, 15:51 Отправитель: CrackLab Отвечает vitya
Здравствуйте, MATRIZA! Я предлагаю волновой алгоритм. Ответ отправлен: 16.06.2004, 16:57 Отправитель: vitya Отвечает bocha
Приветствую Вас, MATRIZA! А тебе лень добавить в тот код, который я вчера отправил три строчки и переписать функцию загрузки матрицы? Если лень то набери в яндексе "алгоритм волны", и найдешь море ссылок Ответ отправлен: 16.06.2004, 18:54 Отправитель: bocha
Форма отправки вопроса
Внимание!
Мы рекомендуем открывать рассылку в программе Internet Explorer 5.0+
или отправлять вопросы с сайта по адресу:
http://rusfaq.ru/cgi-bin/Message.cgi.