Как я могу использовать алгоритм звезды, чтобы найти первые 100 кратчайших путей?

Задача нахождения k-го кратчайшего пути — это NP-Hard, поэтому любая модификация A -Звезда, которая будет делать то, что вам нужно, будет экспоненциальной по размеру ввода.

Доказательство:
(Примечание: я покажу на простых путях)
Предположим, что у вас есть полиномиальный алгоритм, который выполняется за полиномиальное время и возвращает длину kсамого короткого пути. путь пусть алгоритм будет A(G,k)

Максимальное количество путей равно n!, и, применяя бинарный поиск в диапазоне [1,n!], чтобы найти кратчайший путь длиной n, вам потребуется O(log(n!)) = O(nlogn) вызовов A.
Если вы нашли путь длиной n - это гамильтоновский путь.
Повторяя процесс для каждого источника и цели на графике (O(n^2) из них), вы можете решить Задача Гамильтона о путях полиномиально, если такое A существует.
КЭД

Из этого мы можем сделать вывод, что если P=NP (а это очень маловероятно согласно большинству CS исследователи), задача не может быть решена полиномиально.

В качестве альтернативы можно использовать вариант поиска по единой цене без сохранения набора visited/closed. Возможно, вы также сможете изменить A*, отключив закрытые узлы и выдав/сгенерировав найденные решения вместо того, чтобы возвращать их и заканчивать, но я не могу придумать способ доказать это для A. * сейчас.

Помимо того, что эта задача NP-сложная, с A* или dijkstra это невозможно сделать без серьезных модификаций. Вот несколько основных причин:

Во-первых, алгоритм сохраняет на каждом шаге только лучший на данный момент путь. Рассмотрим следующий график:

  A
 / \
S   C-E
 \ /
  B

Примите расстояния d(S,A)=1, d(S,B)=2, d(A,C)=d(B,C)=d(C,E)=10.

При посещении C вы выберете путь через A, но нигде не сохраните путь через B. Так что вам придется сохранить эту информацию.

Но, во-вторых, вы даже не рассматриваете все возможные пути, предположим следующий график:

S------A--E
 \    /
  B--C

Предположим, расстояния d(S,A)=1, d(S,B)=2, d(B,C)=1, d(A,E)=3. Ваш порядок посещения будет {S,A,B,C,E}. Поэтому при посещении A вы даже не можете сохранить объезд через B и C, потому что не знаете об этом. Вам нужно будет добавить что-то вроде «потенциального пути через C» для каждого непосещенного соседа.

В-третьих, вам придется включать циклы и тупики , потому что да, вполне возможно, что путь с петлей окажется одним из ваших 100 кратчайших путей. Вы, конечно, могли бы ограничить это, но это общая возможность. Рассмотрим, например, такие графики:

S-A--D--E
  |  |
  B--C

Понятно, что вы можете легко начать цикл здесь, если вы не запретите «возврат» (например, запретите D->A, если A->D уже находится в пути). На самом деле это даже проблема без явного графического цикла, потому что в общем случае вы всегда можете поиграть в пинг-понг между двумя соседями (путь A-B-A-B-A-...).

А сейчас я, наверное, даже забыл некоторые вопросы.

Обратите внимание, что большинство из этих вещей также очень затрудняют разработку общего алгоритма, особенно последней части, потому что с помощью циклов трудно ограничить количество возможных путей («бесконечный цикл»).

Это не жесткий алгоритм NP, а приведенная ниже ссылка представляет собой алгоритм Йена для вычисления K-кратчайших путей в графе за полиномиальное время. ссылка на алгоритм Йена

Используйте поиск *, когда пункт назначения k-й раз помещается в очередь. Это будет k-й кратчайший путь.