Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.02.2011, 05:08
Новичок

Отправить личное сообщение для Николай_VL Посмотреть профиль Найти все сообщения от Николай_VL
 
Регистрация: 11.02.2011
Сообщений: 1

Поиск k кратчайших путей
Всем доброго времени суток.
Перерыл весь интернет (английский, русский) но найти не смог.

Есть граф (порядка 250 вершин) с неотрицательными весами. Нужно найти k кратчайших путей (k задается) из одной вершины (тоже задается пользователем) во все остальные либо в указанную пользователем.

Нашел два алгоритма: алгоритм двойного поиска (есть в учебнике Гарсиа-Диас "Методы анализа сетей") и алгоритм Йена (хорошего описания не нашел).

Нужно реализовать на С++ или GNU Octave.
Готового найти не удалось, на Ocatve написал (двойного поиска, он же double-sweep algorithm), но в итоге работает неправильно.

Кто может поделиться кодом или подсказать, где его взять.
Спасибо.
  #2  
Старый 04.03.2011, 00:15
Новичок

Отправить личное сообщение для cat_baxter Посмотреть профиль Найти все сообщения от cat_baxter
 
Регистрация: 16.11.2010
Сообщений: 6

Пойдет?
http://code.google.com/p/k-shortest-paths/
 


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

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск всех различных путей в графе. За деньги. velfor Реализация, исходники, языки 0 25.01.2011 17:58
Поиск всех путей в графе Eldar Графы 6 21.05.2009 09:53
Нахождение k кратчайших путей в графе гость Реализация, исходники, языки 4 25.11.2008 14:53
Поиск путей в графе MrFandorin Графы 5 24.04.2008 01:25
Алгоритм поиска k кратчайших путей в графе PhD Графы 3 07.02.2007 02:36