Russian Qt Forum
Ноябрь 23, 2024, 05:45
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Программирование
>
Алгоритмы
>
[РЕШЕНО] Граф. Алгоритм нахождения расстояния м/д вершинами.
Страниц: [
1
]
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: [РЕШЕНО] Граф. Алгоритм нахождения расстояния м/д вершинами. (Прочитано 8572 раз)
gil9red
Administrator
Джедай : наставник для всех
Offline
Сообщений: 1805
[РЕШЕНО] Граф. Алгоритм нахождения расстояния м/д вершинами.
«
:
Июль 03, 2012, 12:33 »
Здравствуйте, форумчане!
Не пинайте меня пожалуйста!!
Нужен алгоритм поиска расстояния м/д вершинами графа,
граф не имеет ориентации и его ребра не имеют веса.
Он ооочень нужен, а в алгоритмах я не очень силен, вообще не силен
Спасибо, заранее
«
Последнее редактирование: Ноябрь 11, 2012, 20:33 от gil9red
»
Записан
https://github.com/gil9red
https://ru.stackoverflow.com/users/201445/gil9red
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #1 :
Июль 03, 2012, 12:41 »
Цитата: gil9red от Июль 03, 2012, 12:33
Не пинайте меня пожалуйста!!
Нужен алгоритм поиска расстояния м/д вершинами графа,
граф не имеет ориентации и его ребра не имеют веса.
Пинать не будем, но скажите что надо. Если заданы ребра и каждая вершина (точка) имеет координату, то чего находить-то? Длины ребер известны. Или Вам надо построить ребра? Или найти путь в графе? Нет задачи - не будет и решений.
Записан
DmitryM
Гость
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #2 :
Июль 03, 2012, 12:45 »
Цитата: gil9red от Июль 03, 2012, 12:33
Здравствуйте, форумчане!
Не пинайте меня пожалуйста!!
Нужен алгоритм поиска расстояния м/д вершинами графа,
граф не имеет ориентации и его ребра не имеют веса.
Он ооочень нужен, а в алгоритмах я не очень силен, вообще не силен
Спасибо, заранее
Алгоритм Дейкстры
Записан
gil9red
Administrator
Джедай : наставник для всех
Offline
Сообщений: 1805
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #3 :
Июль 03, 2012, 13:50 »
Если полное условие, то:
есть файл, в нем:
кол-во вершин
кол-во ребер
связь м\д вершинами
например для графа
связь будет такой:
1->2
2->3
2->4
2->5
3->4
4->5
5->6
нужно вывести расстояние м/д 1 вершиной и всеми остальными
для данного графа, расстояние м/д 1 и 4 вершинами будет 2
Записан
https://github.com/gil9red
https://ru.stackoverflow.com/users/201445/gil9red
gil9red
Administrator
Джедай : наставник для всех
Offline
Сообщений: 1805
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #4 :
Июль 03, 2012, 14:28 »
DmitryM
, я написал что ребра графа не имеют веса, а алгоритм Дейкстры находит находит минимальное расстояние учитывая веса ребер
Записан
https://github.com/gil9red
https://ru.stackoverflow.com/users/201445/gil9red
Patrin Andrey
Гость
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #5 :
Июль 03, 2012, 14:34 »
Ну так представьте, что вес всех рёбер равен.
Записан
gil9red
Administrator
Джедай : наставник для всех
Offline
Сообщений: 1805
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #6 :
Июль 03, 2012, 14:44 »
Patrin Andrey
, в алгоритме Дейкстры это представление не даст ничего хорошего, представим, что нужно найти минимальнй путь скажем от первой вершины до последней, вес у всех равен, следовательно, первый же путь окажется для такого алгоритма истинным (что не всегда хорошо), для условия моей задачи ориентации нет и нет у ребер веса, что определенно облегчает алгоритм поиска, и использовать для его решения Дейкстру не очень рационально, да и как я говорил выше, с генерацией и претворением алгоритмов у меня проблемы
Поэтому я и прошу у вас помощи
Записан
https://github.com/gil9red
https://ru.stackoverflow.com/users/201445/gil9red
Fat-Zer
Гость
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #7 :
Июль 03, 2012, 14:55 »
ОМГ. обычный «поиск в ширину»...
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #8 :
Июль 03, 2012, 15:04 »
Проще написать (аттач) чем объяснять.
gil9red
просьба убрать из названия темы "лень". Если затрудняетесь с какой-то вещью (пусть простой), лучше так и сказать, чем делать вид типа "да я могу но мне лень"
Записан
DmitryM
Гость
Re: Граф. Алгоритм нахождения расстояния м/д вершинами. Лень.
«
Ответ #9 :
Июль 03, 2012, 16:09 »
Цитата: gil9red от Июль 03, 2012, 14:44
Patrin Andrey
, в алгоритме Дейкстры это представление не даст ничего хорошего, представим, что нужно найти минимальнй путь скажем от первой вершины до последней, вес у всех равен, следовательно, первый же путь окажется для такого алгоритма истинным (что не всегда хорошо), для условия моей задачи ориентации нет и нет у ребер веса, что определенно облегчает алгоритм поиска, и использовать для его решения Дейкстру не очень рационально, да и как я говорил выше, с генерацией и претворением алгоритмов у меня проблемы
Поэтому я и прошу у вас помощи
Не смешите мои тапочки. Алгоритм Дейкстры находит кратчайшие пути от одной из вершин до всех. Если принять вес ребра 1, то получишь расстояние от заданной вершины, до любой другой.
Записан
gil9red
Administrator
Джедай : наставник для всех
Offline
Сообщений: 1805
Re: Граф. Алгоритм нахождения расстояния м/д вершинами.
«
Ответ #10 :
Июль 03, 2012, 16:14 »
Igors
, спасибо большое =)
осталось теперь перевести этот код на Java
, но это уже моя забота, да и похожи они синтаксисом
DmitryM
, не буду с вами спорить, я писал предположение, выдвинутое, благодаря знаниям (или их отсутствием, смотря с чем сравнивать), поэтому могу и ошибаться, но по крайней мере материал википедии я читал
Записан
https://github.com/gil9red
https://ru.stackoverflow.com/users/201445/gil9red
kostya2vntu
Гость
Re: Граф. Алгоритм нахождения расстояния м/д вершинами.
«
Ответ #11 :
Июль 04, 2012, 11:24 »
Никакой дейкстры, самый обычный bfs (уже писали - поиск в ширину).
Записан
Страниц: [
1
]
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...