Замечания к заданию 4
Алгоритм, похоже, работает правильно, и я задание зачту. Но всё можно (и нужно) делать гораздо проще.
Точкам, для которых известен хотя бы какой-то путь из начальной точки, присваиваете два состояния: "посещена" или "не посещена". Исходно все считаете непосещёнными, а путь известен только до одной -- до начальной и его вес равен 0.
На каждой итерации алгоритма находите среди непосещённых точек точку с минимальной длиной пути из начальной, обновляете пути для каждого её соседа, если этот сосед ещё не был посещён, саму точку отмечаете посещённой. Делаете так, пока непосещённой точкой с минимальной длиной пути не стала конечная точка.
Это алгоритм Декстры, он простой, оптимален по числу просматриваемых точек и находит наикратчайший путь.
И к нему легко применить двоичное дерево поиска (в нём можно хранить непосещённые точки, упорядоченные по их длине пути), на каждой итерации изывается самый левый лист дерева, находятся соседи точки и их позиции в дереве (для этого можно хранить отдельно для каждой точки указатель на её позицию в дереве, равный nullptr
если точка не в дереве), если путь для соседей оказывается более коротким, то сосед удаляется из дерева (если был в нём) и добавляется в него снова с обновлённой длиной пути.