От каждого начального узла до каждого конечного узла рассчитайте кратчайшее расстояние. Расстояние между узлами 1

Question

Я должен рассчитать кратчайшее расстояние от n начальных узлов до n конечных узлов. Меня не волнует фактический путь. Количество узлов намного больше, чем n. Каждый узел связан ровно с 9 узлами. Расстояние от узла до узла равно 1. Моя лучшая идея для этого - сделать поиск в ширину для начального узла, который, если я правильно понимаю, даст мне n конечного расстояния в линейном времени, и я бы сделал это для каждого начального узла.

Есть ли более быстрый подход к этому?

Редактировать: полная проблема в том, что у меня есть 2-й гоночный трек, финишная линия sh и машина, которая должна делать число кругов, и автомобиль может иметь только 121 различных векторов скорости, поэтому vx = [- 5,5], vy = [- 5,5] и может изменять только свой вектор скорости + -1 каждый тик. Также автомобиль не должен врезаться в стены. Я хочу рассчитать точное кратчайшее время (тик), которое он может сделать на этих кругах. Моя идея состояла в том, чтобы создать узлы из пар скоростей-позиций и рассчитать кратчайший путь от каждой скорости в каждой точке линии конечного положения sh до каждой пары скоростных позиций в той же линии конечного положения sh. А затем используйте эти данные, чтобы выполнить отдельный поиск пути для заданного количества кругов, зная стартовую позицию автомобиля.

Answer 1

да, используйте алгоритм кратчайшего пути Джикстры:

1) Создайте набор sptSet (набор дерева кратчайшего пути), который отслеживает вершины, включенные в дерево кратчайшего пути, т. Е. Минимальное расстояние от источника которого рассчитывается, и завершена. Первоначально этот набор пуст.

2) Присвойте значение расстояния всем вершинам входного графа. Инициализируйте все значения расстояния как БЕСКОНЕЧНЫЙ. Присвойте значение расстояния 0 для исходной вершины, чтобы она выбиралась первой.

3) Хотя sptSet не включает в себя все вершины

… .a) Выберите вершину u, которой нет в sptSet и имеет минимальное значение расстояния.

… .b) Включить u в sptSet.

…. c) Обновить значение расстояния всех смежных вершин u. Чтобы обновить значения расстояния, выполните итерацию по всем смежным вершинам. Если для каждой смежной вершины v сумма значений расстояния u (от источника) и веса ребра uv меньше значения расстояния v, обновите значение расстояния v.