Он будет немного большим, так как я все объясню. Вот ссылка на очень простую и прямую задачу алгоритма Дейкстры, чтобы попробовать и

"решение"

Пожалуйста, прочитайте немного теории Дейкстры в Интернете или в какой-нибудь книге, надеюсь, вы легко ее найдете.

Объяснение кода выглядит следующим образом:

**Что нужно сделать (в задаче)››› Требуется найти кратчайший путь от вершины 1 до последней, т.е. количество вершин равно последней, так как они пронумерованы последовательно от 1 до n (n=количество вершин), т.е. найти кратчайший путь от первой вершины до n-й вершины.

1) Имейте массив путей, заполните его от 1 до n бесконечностью (очень высокое значение) (изолируя их, согласно алгоритму, не представляя ни одного, связанного ни с кем.

2) Поскольку я буду выполнять возврат, чтобы найти путь, поэтому массив с именем parent будет хранить родительский элемент каждого узла (чтобы знать, откуда мы пришли), изначально родительский элемент корневого/начального узла, т.е. startV будет '-1 ', и будет использовать его для остановки итерации (позже поясняется) — (просто говоря, что начальный узел не имеет родителя, остальное мы рассчитаем)

3) Затем вызывает Dijkstra(), а затем функцию print_path().

Объяснение Дейкстры звучит так:

1) очередь кратчайшего пути - это приоритетная очередь, которая будет удерживать вес, а затем к какому узлу этот вес относится имя узла (фактически номер) в паре, соответствующей порядку как ‹вес,узел›, в порядке убывания веса, как правило, дается наивысший приоритет, но он будет удерживать минимум наверху, используя Greater‹int›() в определении приоритетной очереди (pq=приоритетная очередь), google остает синтаксис pq

2) Функция Дейкстры имеет однократную инициализацию pq, удерживая 0 веса/расстояния до startV (без учета случаев самозацикливания)

— — — — Согласно алгоритму, мы вычисляем расстояния между соседними узлами всех ожидающих узлов и проходим минимальное среди них всех, pq удержит их все и будет иметь мин. вверху, поэтому нам не нужно будет искать min среди них всех, это ускорит поиск и уменьшит сложности (обратите внимание: мы не обходим текущие узлы, соседние с min, а среди всех ожидающих узлов adj.’s)

— — — — Мы вернем 0 из функции поиска кратчайшего пути в случае, если все узлы были пройдены, и мы закончили, или нам нечего проходить до currV, т.е. текущей вершины, поэтому в случае, если мы достигли любого endV (желаемого) вершине или нечего обходить, мы вернемся. т. е. если currV==endV или currV=0, то вернуть

3) вызвать функцию find_shortest(), чтобы найти самый короткий среди ожидающих узлов. Поскольку до сих пор pq имеет только узел 1, то есть начальный узел с расстоянием 0 (pq содержит ожидающие/временные узлы, минимальное расстояние которых еще не определено), функция возвращает вершину pq и выталкивает вершину, это делает следующий ожидающий узел как самый короткий.

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

5) если путь currV, т.е. 1, который является родительским плюсом (+) для каждого его adj, т.е. дочерним, меньше, чем путь, пока не будет найден этот конкретный дочерний элемент, мы обновим его дочерний путь вместе с его родителем как «currV», который равен 1 для первая итерация и поместите ее в pq , то есть в список ожидания (мы инициализировали путь бесконечностью, изолированным, у нас есть меньший путь для первой итерации)

6) установите его путь, нажмите на pq и обновите его родителя

7) Продолжайте делать это, обновляя и дорабатывая путь к вершине pq на каждой итерации.

8) если pq пуст, это означает, что нет ребра, соединяющего нас с конечным узлом (любым другим узлом), или мы являемся узлом, повторяющим все узлы, и нет точки, повторно посещающей узлы, для которых конечные расстояния установлены на true.

9) или в случае, если currV==endV — это то ребро, которое нам нужно. мы возвращаемся. Теперь каждое ребро должно иметь родителя. если мы достигли endV, то есть нашего желаемого V , он также должен иметь родителя, иначе 0, будучи глобальным, будет содержать 0 как значение по умолчанию.

Печать пути

Мы вызовем printpath, и если endV имеет родитель как 0, мы закончили (путь невозможен), иначе мы напечатаем endV, затем его родителя и так далее, пока не достигнем -1 как родителя startV

Если вы ищете простой алгоритм Дейкстры. без приоритетной очереди (pq) в верхней части решения я предоставил ссылку на мой сбойный код, один тестовый пример 31, лимит времени превышен TLE, так как это заняло слишком много времени, не стесняйтесь проверить это.