Вход на сайт
Алгоритм поиска длинейшего пути в графике.
305 просмотров
Перейти к просмотру всей ветки
Уже 2 дня ломаю голову. Вздрагиваю при взглюде на любую карту. Перерыл теорию графиков. Нашел множество алгоритмов на нахождение коротчайшего пути в графике без циклов. А с циклами вооще неодного. Может быть кто нибудь сталкивался с похожей задачей. Или знает где найти информацию. Предложениям и идеям буду рад.
Задача выглядит примерно так.
Дано= Ненаправленный циглический график. Тоесть растояние от А на А не всегда =0 и от А на Б может быть несколько возможных путей.
Задача= Найти длинейший путь. Так что бы кажое соединение было только один раз.(Как бы нарисовать неотрывая руки ) К примеру если есть A->A>0 тогда выбирать этот путь. И если есть несколько возможностей А->Б то выбирать длинейший.
Структура данных выглядит так:
Knote{ int ID}
Kante {Knote a , Knote b , int laenge}
Graph{ArrayList <Kante> kanten }
Задача выглядит примерно так.
Дано= Ненаправленный циглический график. Тоесть растояние от А на А не всегда =0 и от А на Б может быть несколько возможных путей.
Задача= Найти длинейший путь. Так что бы кажое соединение было только один раз.(Как бы нарисовать неотрывая руки ) К примеру если есть A->A>0 тогда выбирать этот путь. И если есть несколько возможностей А->Б то выбирать длинейший.
Структура данных выглядит так:
Knote{ int ID}
Kante {Knote a , Knote b , int laenge}
Graph{ArrayList <Kante> kanten }