|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
01.11.2010, 19:51 | #1 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
Кратчайший путь между двум вершинами
Помогите плиз с решением куска задачи:
У меня есть массив векторов g[5000] с описанием графа, нгужно найти кратчайшее расстояние между вершиной 1 и вершиной n. Уже полчаса гуглил, никакого конкретного кода не нашел. |
01.11.2010, 22:05 | #2 |
Старожил
Регистрация: 29.09.2009
Сообщений: 9,713
|
посмотрите в сторону алгоритма Дейкстры, например ...очень доходчиво об этом в статье Уткина в №3 журнала нашего Клуба (см. подпись), думаю проблем с переводом на си при понимании самих принципов у вас не возникнет.
Разработки и научно-технические публикации :: Видеоблог :: Твиттер
Radar systems engineer & Software developer of industrial automation |
02.11.2010, 19:22 | #3 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
Дейкстру то я понимаю примерно на уровне псевдокода, но не могу закодить так, чтобы ф-я мне возвращала путь от начальной вершины до искомой вершины, т.е. получается массив предков искомой вершины, относительно начальной.
|
02.11.2010, 22:03 | #4 |
Старожил
Регистрация: 29.09.2009
Сообщений: 9,713
|
лучше статью почитайте.
Разработки и научно-технические публикации :: Видеоблог :: Твиттер
Radar systems engineer & Software developer of industrial automation |
04.11.2010, 20:24 | #5 |
Форумчанин
Регистрация: 30.07.2009
Сообщений: 256
|
Статью почитал, потом погуглил и понял, что в моем случае больше волновой алгоритм подходит, сейчас думаю над его реализацией.
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
кратчайшие расстояния между вершинами | 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 |