Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

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

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

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

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

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

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


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