Логическая задача (графы)

[art1es23]

Буду очень рад каким-нибудь подсказкам(советам) по поводу решения этой задачи.

Найдите в этом лабиринте такой маршрут, чтобы сумма всех "собранных" на перекрестках чисел была равна 40. Через каждый перекресток можно проходить только один раз.

Я только понял, что решать её надо алгоритмом Дейкстры, но как его реализовать для даной задачи хз.(по-крайней мере мне так кажется)

[Serge_Bliznykov]

Не, думаю, что Дейкстра тут не поможет. В основном алгоритмы поиска пути ищут кратчайший путь. А здесь нужно найти все пути и взять тот, где сумма равна заданному значению

посмотрите методичку - http://kuimova.ucoz.ru/modul_10-graf..._algoritmy.pdf
на 10 странице рассматривается поиск всех путей в графе:

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