Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы
Старый 01.11.2010, 20:51   #1
Gapro
Форумчанин
 
Регистрация: 30.07.2009
Адрес: Екатеринбург
Сообщений: 256
Репутация: 26

icq: 452-608-390
Вопрос Кратчайший путь между двум вершинами

Помогите плиз с решением куска задачи:
У меня есть массив векторов g[5000] с описанием графа, нгужно найти кратчайшее расстояние между вершиной 1 и вершиной n. Уже полчаса гуглил, никакого конкретного кода не нашел.
Gapro вне форума   Ответить с цитированием
Старый 01.11.2010, 23:05   #2
raxp
Профессионал
 
Регистрация: 29.09.2009
Сообщений: 9,731
Репутация: 3006
По умолчанию

посмотрите в сторону алгоритма Дейкстры, например ...очень доходчиво об этом в статье Уткина в №3 журнала нашего Клуба (см. подпись), думаю проблем с переводом на си при понимании самих принципов у вас не возникнет.
__________________
Разработки и научно-технические публикации :: Видеоблог :: Твиттер
Radar systems engineer & Software developer of industrial automation
raxp вне форума   Ответить с цитированием
Старый 02.11.2010, 20:22   #3
Gapro
Форумчанин
 
Регистрация: 30.07.2009
Адрес: Екатеринбург
Сообщений: 256
Репутация: 26

icq: 452-608-390
По умолчанию

Дейкстру то я понимаю примерно на уровне псевдокода, но не могу закодить так, чтобы ф-я мне возвращала путь от начальной вершины до искомой вершины, т.е. получается массив предков искомой вершины, относительно начальной.
Gapro вне форума   Ответить с цитированием
Старый 02.11.2010, 23:03   #4
raxp
Профессионал
 
Регистрация: 29.09.2009
Сообщений: 9,731
Репутация: 3006
По умолчанию

лучше статью почитайте.
__________________
Разработки и научно-технические публикации :: Видеоблог :: Твиттер
Radar systems engineer & Software developer of industrial automation
raxp вне форума   Ответить с цитированием
Старый 04.11.2010, 21:24   #5
Gapro
Форумчанин
 
Регистрация: 30.07.2009
Адрес: Екатеринбург
Сообщений: 256
Репутация: 26

icq: 452-608-390
По умолчанию

Статью почитал, потом погуглил и понял, что в моем случае больше волновой алгоритм подходит, сейчас думаю над его реализацией.
Gapro вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
кратчайшие расстояния между вершинами pum-pum-pum Помощь студентам 1 07.01.2010 12:30
Кратчайшее расстояние между всеми вершинами ooooch Помощь студентам 5 15.11.2009 16:36
Графы (кратчайший путь и обход ВСЕХ вершин) 08ekhiv1 Помощь студентам 5 05.08.2009 13:12
Найти кратчайший путь между точками lucky Общие вопросы Delphi 0 27.05.2009 07:26


18:48.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru