Кратчайшее расстояние пути между точками, заданными как координаты X-Y

Любой алгоритм поиска пути зависит от путей, точки просто бессмысленны. Теперь у вас есть список «путевых точек». Однако вы не объяснили, как эти точки соединяются. Например, если любая и каждая точка соединена друг с другом, кратчайшее расстояние будет просто пифагоровым расстоянием между A и B. - Я также не уверен, что вы подразумеваете под координатами X-Y электрических линий, такая «линия» всегда будет есть начальная и конечная позиция?

Итак, первый шаг — добавить к каждой точке не только координаты x,y, но и список соединяемых точек.

Как только вы это сделаете, вы можете начать использовать алгоритм поиска пути (хотя в этом случае A * будет лучше, чем алгоритм Дейкстры). Это была бы просто стандартная реализация с каждой «стоимостью» фактического расстояния между точками. (А для A* эвристикой будет пифагорическое расстояние до конечной точки).

Чтобы получить хороший учебник по A* (и другим алгоритмам), вы должны проверить страницы Амита.

РЕДАКТИРОВАТЬ, в ответ на комментарии.

Кажется, первый шаг — преобразовать набор отрезков в «точки». Я бы прошел через это:

collection AllPoints {containing Location & LinksToOtherPoints}
for each Segment
    get start/end Point of Segment
    if Point.Location is not in allPoints
        add Point to AllPoints
    add the other Point of Segment to LinksToOtherPoints

Затем у вас есть просто список со всеми точками и соединениями между ними. Поскольку вам нужно постоянно искать коллекцию allPoints, я предлагаю хранить ее в двоичной древовидной структуре (наборах?).

Для вычисления кратчайшего пути Диякстра подойдет.

Вы можете получить более быстрые результаты, используя A*, который использует наилучшее предположение о расстоянии в чтобы сфокусировать свой поиск в нужном направлении, тем самым быстрее туда добраться.

Если вы повторно запрашиваете один и тот же набор данных, то запоминание подойдет.

Те люди, которые рекомендуют алгоритм грубой силы, — дураки — стоит потратить немного времени, чтобы научиться программировать эффективное решение. Но вы можете рассчитать кратчайший путь между всеми точками, используя алгоритм Флойда-Уоршалла. К сожалению, это не скажет вам, каков кратчайший путь, а только насколько он длинный.

Просто рассчитайте расстояние для всех возможных путей и выберите самый короткий. 800 путей для современного ПК - это ничто. Вы даже не заметите этого.