|
Поиск k кратчайших путей
Всем доброго времени суток.
Перерыл весь интернет (английский, русский) но найти не смог.
Есть граф (порядка 250 вершин) с неотрицательными весами. Нужно найти k кратчайших путей (k задается) из одной вершины (тоже задается пользователем) во все остальные либо в указанную пользователем.
Нашел два алгоритма: алгоритм двойного поиска (есть в учебнике Гарсиа-Диас "Методы анализа сетей") и алгоритм Йена (хорошего описания не нашел).
Нужно реализовать на С++ или GNU Octave.
Готового найти не удалось, на Ocatve написал (двойного поиска, он же double-sweep algorithm), но в итоге работает неправильно.
Кто может поделиться кодом или подсказать, где его взять.
Спасибо.
|
Линейный вид
