Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
pma11
1 / 1 / 0
Регистрация: 24.04.2013
Сообщений: 24
1

Поиск кратчайшего пути в графе

07.11.2013, 16:58. Просмотров 899. Ответов 4
Метки нет (Все метки)

Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в графе. Также существует условие, что при проходе по некоторым ребрам (известны заранее) некоторые другие ребра могут либо появляться, либо исчезать (также известно заранее). Подскажите, какие алгоритмы обхода помогут корректно решить данную задачу?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2013, 16:58
Ответы с готовыми решениями:

Поиск кратчайшего пути
Всем доброго времени суток! Скажите, пожалуйста. Есть ли какие-то принципиальные отличия волнового...

Поиск кратчайшего пути в лабиринте
Пишу программу для нахождения (и вывода) кратчашего пути в лабиринте, заданном в текстовом файле в...

АСтар поиск кратчайшего пути
Здравствуйте знаю что подобных тем сотни, но я никак не могу разобраться в двух вещах. Я пытаюсь...

Поиск кратчайшего пути в лабиринте
Добрый день, знаю два алгоритма. 1. А - стар 2. Волновой Нужен какой нибудь 3... Ссылки...

Поиск кратчайшего пути лошадью
(p, q)-лошадь - это обобщение обычного шахматного коня. (p, q)-лошадь своим ходом перемещается на p...

4
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
07.11.2013, 17:29 2
тот же Дейкстра, только надо каждый раз чекать ребро на валидность.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
07.11.2013, 17:52 3
Цитата Сообщение от pma11 Посмотреть сообщение
поиск кратчайшего пути между двумя заданными вершинами в графе
А граф взвешенный?

Цитата Сообщение от salam Посмотреть сообщение
тот же Дейкстра, только надо каждый раз чекать ребро на валидность.
А по-моему, тут условия применимости нарушаются, по крайней мере одно из трёх...
А вообще, думать надо, так сразу сложно сказать...
0
pma11
1 / 1 / 0
Регистрация: 24.04.2013
Сообщений: 24
07.11.2013, 19:02  [ТС] 4
Qwertiy, граф неориентированный и невзвешенный. Я смотрю в сторону алгоритма Форда-Беллмана
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
08.11.2013, 10:32 5
Пока только мысли. Если мы проходим через какое-то ребро (в том числе, ребро-переключатель), то мы доходим до него некоторым оптимальным способом. Оптимальным в том же плане, что и искомый путь. Тогда можно запускать поиск и смотреть, в какие рёбра мы можем придти и как-то строить новый граф или перезапускать поиск.
0
08.11.2013, 10:32
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2013, 10:32

Двунаправленный поиск кратчайшего пути в графах
Никто не встречал реализованный на c\c++ алгоритм? Добавлено через 17 часов 24 минуты помогите...

Поиск кратчайшего пути в матрице или установка факта, что такового не существует
Всем привет!!!я начал решать задачку и у меня не получается, а не получается у меня самое главное...

Поиск пути на графе — "муравьед"
Привет Необходимо реализовать этот алгоритм. Язык не важен, исходные данные пока не важны. Суть...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.