|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
15.01.2017, 00:55 | #1 |
Новичок
Джуниор
Регистрация: 15.01.2017
Сообщений: 4
|
Самый длинный (максимальный) путь в графе - Java SE
Подскажите, пожалуйста, как можно изменить алгоритм Дейкстры (Dijkstra), чтобы найти самый длинный путь (наибольшая сумма веса ребер) в графе от определенной стартовой вершины, пройдя ВСЕ вершины. Или какой другой алгоритм можно использовать? Граф без циклов и без ребер с отрицательным весом. Например для графа представленного в виде данной матрицы смежности:
0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 Стартовая вершина 1. На выходе необходимо получить приблизительно в таком формате ответ: Максимальный путь 1: 1 3 2: 1 2 3: 2 4 Общее время - 3 ед. Минимальный путь 1: 1 2 2: 1 3 и 2 4 Общее время - 2 ед. ========================= У меня есть такой какой код: Код:
|
15.01.2017, 18:38 | #2 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Думаю, что вам нужен алгоритм поиска Гамильтонова пути (не цикла, именно пути). А это по сути полный перебор с запоминанием лучшего варианта.
Т.е. берёте обход в глубину и измняете его под собственные нужды - т.е. когда "погружение" больше невозможно проверяете ситуацию, что все вершины посещены, и если посещены, то запоминаете и лучший результат и путь к его достижению. Но хочу уточнить. Дело в том, что иногда студенты, изучая алгоритм Дейкстры, изучают и понятие "диаметр графа". Так этот диаметр совершенно не равен длине максимального Гамильтонова пути. Так вам нужно искать максимальный Гамильтонов путь или диаметр графа? |
16.01.2017, 00:15 | #3 |
Новичок
Джуниор
Регистрация: 15.01.2017
Сообщений: 4
|
Может я чуть не так написал... в общем мне нужно найти максимальное и минимальное время за которое все элементы графа получат сигнал, при этом за одну единицу времени сигнал могут отправлять n количество НЕ связанных между собой элементов
т.е. на каждом уровне дерева элементы (к котороым уже дошел сигнал) могут работать одновременно. |
16.01.2017, 01:20 | #4 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
|
16.01.2017, 01:31 | #5 |
Новичок
Джуниор
Регистрация: 15.01.2017
Сообщений: 4
|
Если сигнал выходит из 1 к 2 это считается как 1 единица времени , за вторую сигнал уже может выходить из 2 и из 1 если у неё есть соединение с какой-то еще вершиной.
Например из графа в примере, минимальное время и лучший вариант - это если сигнал с 1 идет к 2 (одна секунда грубо говоря), а потом одновременно с 2 в 4 и с 1 в 3 (вторая секунда) Минимальный путь 1: 1 2 2: 1 3 и 2 4 Общее время - 2 ед. А худший вариант, если сигнал начнет свой путь от 1 к 3 (1 сек), потом от 1 к 2 (вторая сек), потом от 2 к 4 (третья сек). Максимальный путь 1: 1 3 2: 1 2 3: 2 4 Общее время - 3 ед. Из одной вершины может идти одновременно 1 сигнал, при этом из разных n количество. |
16.01.2017, 07:50 | #6 | |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Эта часть фразы не полностью ясна
Цитата:
По максимальному времени. Из примера не ясно, обязательно ли распространение изо всех посещённых вершин или можно на каждом шаге посещать лишь одну новую вершину. Если требуется обязательное распространение из всех посещённых - то нужно найти диаметр графа (алгоритм Флойда-Уоршелла + поиск в результатах максимального пути = диаметра графа). Если одновременное распространение не обязательно - то максимальный путь равен (n-1). Возможно, есть смысл проконсультироваться у преподавателя или получить подсказку из методички (к данной лабораторке). |
|
16.01.2017, 15:05 | #7 |
Новичок
Джуниор
Регистрация: 15.01.2017
Сообщений: 4
|
Распространение изо всех посещённых вершин - обязательно. Диаметр графа мне в принципе находит алгоритм Дейкстры (который выше). В данном примере это 2. Это получается минимальный путь для ответа задачи (максимальный 3). А если для например для графа в приложении, то диаметр будет 4. Пока сигнал идет по пути 1 2 8 5 9, из других вершин сигнал идет к другим вершинам.
The best case: the total time is 4 units of time. 0 1 1 2 3 2 2 2 4 3 1: 1 2: 1 2 3: 1 3 4: 1 2 4 5: 1 2 8 5 6: 1 3 6 7: 1 3 7 8: 1 2 8 9: 1 2 8 5 9 10: 1 3 7 10 А максимальный не будет n-1. А если мы выберем после 1 не 2, а 3 например, то путь может быть длиннее и вот надо найти худший выбор пути. |
16.01.2017, 20:45 | #8 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Честно - ничего кроме перебора в голову не приходит.
А на каком сайте проверяете? Там нет подсказок в обсуждении? |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
(с++) Кратчайший путь в графе | Uefa | Помощь студентам | 15 | 04.12.2013 15:50 |
Как найти максимальный подграф или клику в неориентированном графе?(PASCAL)) | Artur1992 | Помощь студентам | 0 | 17.02.2011 16:31 |
Минимальный путь в графе | marin@ | Помощь студентам | 0 | 11.12.2010 19:53 |
Минимальный путь в графе | Sarumjan | Помощь студентам | 1 | 19.11.2010 07:17 |