Russian Qt Forum
Ноябрь 23, 2024, 05:45 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: [РЕШЕНО] Граф. Алгоритм нахождения расстояния м/д вершинами.  (Прочитано 8572 раз)
gil9red
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 1805



Просмотр профиля WWW
« : Июль 03, 2012, 12:33 »

Здравствуйте, форумчане!
Не пинайте меня пожалуйста!!  Улыбающийся
Нужен алгоритм поиска расстояния м/д вершинами графа,
граф не имеет ориентации и его ребра не имеют веса.
Он ооочень нужен, а в алгоритмах я не очень силен, вообще не силен Улыбающийся
Спасибо, заранее Улыбающийся
« Последнее редактирование: Ноябрь 11, 2012, 20:33 от gil9red » Записан

Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #1 : Июль 03, 2012, 12:41 »

Не пинайте меня пожалуйста!!  Улыбающийся
Нужен алгоритм поиска расстояния м/д вершинами графа,
граф не имеет ориентации и его ребра не имеют веса.
Пинать не будем, но скажите что надо. Если заданы ребра и каждая вершина (точка) имеет координату, то чего находить-то? Длины ребер известны. Или Вам надо построить ребра? Или найти путь в графе? Нет задачи - не будет и решений. 
Записан
DmitryM
Гость
« Ответ #2 : Июль 03, 2012, 12:45 »

Здравствуйте, форумчане!
Не пинайте меня пожалуйста!!  Улыбающийся
Нужен алгоритм поиска расстояния м/д вершинами графа,
граф не имеет ориентации и его ребра не имеют веса.
Он ооочень нужен, а в алгоритмах я не очень силен, вообще не силен Улыбающийся
Спасибо, заранее Улыбающийся
Алгоритм Дейкстры
Записан
gil9red
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 1805



Просмотр профиля WWW
« Ответ #3 : Июль 03, 2012, 13:50 »

Если полное условие, то:
есть файл, в нем:
  • кол-во вершин
  • кол-во ребер
  • связь м\д вершинами

например для графа
связь будет такой:
1->2
2->3
2->4
2->5
3->4
4->5
5->6

нужно вывести расстояние м/д 1 вершиной и всеми остальными

для данного графа, расстояние м/д 1 и 4 вершинами будет 2
Записан

gil9red
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 1805



Просмотр профиля WWW
« Ответ #4 : Июль 03, 2012, 14:28 »

DmitryM, я написал что ребра графа не имеют веса, а алгоритм Дейкстры находит находит минимальное расстояние учитывая веса ребер
Записан

Patrin Andrey
Гость
« Ответ #5 : Июль 03, 2012, 14:34 »

Ну так представьте, что вес всех рёбер равен.
Записан
gil9red
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 1805



Просмотр профиля WWW
« Ответ #6 : Июль 03, 2012, 14:44 »

Patrin Andrey, в алгоритме Дейкстры это представление не даст ничего хорошего, представим, что нужно найти минимальнй путь скажем от первой вершины до последней, вес у всех равен, следовательно, первый же путь окажется для такого алгоритма истинным (что не всегда хорошо), для условия моей задачи ориентации нет и нет у ребер веса, что определенно облегчает алгоритм поиска, и использовать для его решения Дейкстру не очень рационально, да и как я говорил выше, с генерацией и претворением алгоритмов у меня проблемы  Улыбающийся
Поэтому я и прошу у вас помощи Улыбающийся
Записан

Fat-Zer
Гость
« Ответ #7 : Июль 03, 2012, 14:55 »

ОМГ. обычный «поиск в ширину»...
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Июль 03, 2012, 15:04 »

Проще написать (аттач) чем объяснять.

gil9red просьба убрать из названия темы "лень". Если затрудняетесь с какой-то вещью (пусть простой), лучше так и сказать, чем делать вид типа "да я могу но мне лень"  Улыбающийся
Записан
DmitryM
Гость
« Ответ #9 : Июль 03, 2012, 16:09 »

Patrin Andrey, в алгоритме Дейкстры это представление не даст ничего хорошего, представим, что нужно найти минимальнй путь скажем от первой вершины до последней, вес у всех равен, следовательно, первый же путь окажется для такого алгоритма истинным (что не всегда хорошо), для условия моей задачи ориентации нет и нет у ребер веса, что определенно облегчает алгоритм поиска, и использовать для его решения Дейкстру не очень рационально, да и как я говорил выше, с генерацией и претворением алгоритмов у меня проблемы  Улыбающийся
Поэтому я и прошу у вас помощи Улыбающийся
Не смешите мои тапочки. Алгоритм Дейкстры находит кратчайшие пути от одной из вершин до всех. Если принять вес ребра 1, то получишь расстояние от заданной вершины, до любой другой.
Записан
gil9red
Administrator
Джедай : наставник для всех
*****
Offline Offline

Сообщений: 1805



Просмотр профиля WWW
« Ответ #10 : Июль 03, 2012, 16:14 »

Igors, спасибо большое =)
осталось теперь перевести этот код на Java Улыбающийся, но это уже моя забота, да и похожи они синтаксисом Улыбающийся

DmitryM, не буду с вами спорить, я писал предположение, выдвинутое, благодаря знаниям (или их отсутствием, смотря с чем сравнивать), поэтому могу и ошибаться, но по крайней мере материал википедии я читал Улыбающийся
Записан

kostya2vntu
Гость
« Ответ #11 : Июль 04, 2012, 11:24 »

Никакой дейкстры, самый обычный bfs (уже писали - поиск в ширину).
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.131 секунд. Запросов: 22.