// x,y - точка от которой ищем +1м вверх
// -180 <=x<=180, -90<=y<=90.
l = 0
// required_dist - нужное приращение
r = min(180, 90-y);
while r-l < 1e-10:
m=(r+l)/2;
dist = haversine((x,y),(x,y+m)); // Формула для расстояния между точками.
if dist > required_dist: r = m
else l = m
step = l; // шаг по широте, чтобы сдвинутся на required_dist.newdistance, а -newdistance.
for (var child of graph[startNode].keys()) не нужен.
У вас ребра вперед и назад разной длины, есть связь всех вершин с четвертой, а она назад только с третьей. Но дейкстра и в ориентированных графах работет, так что это не проблема.
Дабавьте еще вывода туда, где newDistance считается и в очереди что-то обновляется или добавляется. Проблема там, где второй раз выводится current_node 1. Видимо на предыдущей итерации он ее добавляет в очередь из дуги 1=>3
Как он ей делает distance = 3? Ведь в начале вы делаете distances.set(startNode, 0); и только уменьшаете расстояние.
Видимо косяк в этом коде:
когда child[0] == 1, distances[1] ==0, newdistance ==3 он переписывает. Проверьте приоритет операций, что возвращает !distances.get(). Пройдитесь дебаггером.