Вполне возможно реализовать алгоритм Дейкстры без обратных указателей;Я знаю это, потому что Я сделал это сам .:-) В результате вы не сможете восстановить кратчайшие пути, как только закончите, но если все, что вам нужно, это длины пути, которые должны быть идеально хорошими.
Что касается вашего второго вопросаДа, вы можете просто использовать BFS напрямую с удельным весом.Алгоритм Дейкстры посещает узлы в том порядке, в котором они встречаются в BFS, если все ребра имеют одинаковую положительную стоимость.