Как найти ВСЕ кратчайшие пути между двумя вершинами?
А зачем?
Представь себе шахматную доску, твои вершины - клетки, рёбра - границы смежных клеток и только они, переход шаг_влево/шаг_вправо/шаг_вверх/шаг_вниз.
Сколько существует кратчайших путей с левой нижней клетки в правую верхнюю? спойлер: 3432
А если вообразить аналогичный трёхмерный куб? 399072960
Вывод: задача хреново поставлена.
UPDATE
Для наглядности, пусть из одной из нужных вершин выходят 3 грани. 
Строишь кратчайший путь, он проходит через первую из 3 граней. Путь запоминаешь, грань перерезаешь. 
Строишь кратчайший путь, он проходит через вторую грань. Если он равновелик первому - запоминаешь, вторую грань  перерезаешь, если больше - вторую и третью грани можешь совсем выкинуть.
Достаёшь первый путь, восстанавливаешь первую грань, идёшь по пути дальше до вершины с развилкой. режешь грань кратчайшего пути - ну, понятно, рекурсия.
На вырожденном графе, как я и обещал, хана.
первая же ссылка у гугла
Не оно?