Мне кажется, что удобнее всего использовать обход в ширину. Записывая вес и путь до каждой встретившейся вершины.
В конечной точке соберутся все варианты.
Только эта штука будет жутко кушать память и не помешало бы сделать некоторые оптимизации:
-удалять/не записывать более длинные пути
-обьединять при дальнейшем поиске пути "слившиеся" в одной вершине
(Это то, что сразу приходит на ум, может есть ещё какие-то варианты)