Подскажите алгоритм обхода графа

Всем привет! Подскажите, пожалуйста, какой алгоритм лучше справится с задачей нахождения нескольких лучших путей обхода графа? Граф описан ниже

- Граф циклический
- Веса у ребер могут быть как положительными, так и отрицательными. Отрицательных меньше.

Представить граф можно примерно так. Есть несколько "систем" (буквы), в каждой системе есть несколько элементов (цифры). Между одинаковыми элементами разных система есть ребра (например а1-б1, а4-б4). И также а каждой системе есть "главные" элементы, к которым есть ребра ото всех элементов (Например а1. От него есть ребра к а2, а3, а4 и т.д.). Это показано на схеме ниже:



Но элемент, который связан со всеми, на схеме не один. Их там от двух до пяти (a1, a2, а3, б1, б2, б3 на схеме ниже)



Ну и систем (букв) будет больше (от трех до 5), а также элементов по штук 30. В итоге получается чуть похуже, чем на схеме ниже:



Задача такая: надо найти несколько самых дешевых путей обхода (штук 5 лучших). Начинаем из заданной точки, в неё и возвращаемся. По одному и тому же ребру дважды проходить нельзя. Путь может содержать максимум 10 вершин, дальше не ищем (чтобы совсем уж бесконечное количество вариантов не было).

Получается, так как веса могут быть отрицательными, нужно найти такой путь, который находит максимально отрицательные ребра и пытается пройти через них, максимально не попадая на слишком положительные. Как-то так =D

Хотелось бы найти алгоритм, который со всем этим справится не больше, чем за минуту.

Есть идеи?

0

Ну я бы пробовал начать с алгоритма обхода графа в глубину. С его помощью найти все маршруты из данной вершины (с возвращением в нее же). И после этого, среди найденных найти пять оптимальных.

0

ROS88, то есть, получается, выполнять алгоритм отдельно для каждого варианта длины пути?

Добавлено через 58 минут
А нет, понял, туплю)
У меня вот как раз были опасения по поводу производительности всего этого дела. Ну, попробую закодить - скажу

0

ROS88, в общем сгенерил простенький граф типа того, что на втором рисунке. 2 буквы - а и б, по 20 элементов в каждой, и всего лишь по 2 элемента связаны со всеми остальными.


- хотел было уже я написать, но с чего-то вдруг решил проверить поиск на старой, неоптимизированной версии. И там результат оказался при глубине 9 - 7 секунд, при 10 - 35 сек.

Дело в том, что я пишу на функциональном ЯП и там использование мутабельных коллекций считается оптимизационным решением (и обычно циклы на мутабельных коллекциях действительно работают быстрее), но у меня почему-то получилось наоборот =D То ли руки у меня кривые, то ли что...

Но учитывая то, что пути надо будет искать из всех точек (а не из одной, как сейчас), а рабочий граф будет больше, то стартап тайм всё равно будет гигантским (прога ищет эти пути на старте программы. Потом ими пользуется). Но всё же это лучше, чем ничего.

Как думаете, пробовать копать в сторону хвостовой рекурсии? Или это только замедлит поиск?

0

Попробуйте алгоритм Дейкстры модифицировать под свою задачу.

0