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

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

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


Ответ
 
Опции темы
Старый 01.11.2010, 20:51   #1
Gapro
Форумчанин
 
Регистрация: 30.07.2009
Сообщений: 256
Вопрос Кратчайший путь между двум вершинами

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

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

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

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

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

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
кратчайшие расстояния между вершинами 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