Алгоритм «Алгоритм Дейкстры»

кратчайший путь

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

Например, в Шанхае доберитесь до определенного места на метро.В Шанхае много линий метро, ​​и на карте это выглядит как сеть. Будет несколько маршрутов на выбор, чтобы куда-то добраться, и мы обычно выбираем кратчайший маршрут. Конечно, в реальной жизни будут учитываться и такие факторы, как время и трансфер, вот лишь пример того, что такое кратчайший путь.

На первый взгляд, пересадка на метро кажется лучшим маршрутом. Однако в некоторых сложных ситуациях человеческому глазу сложно определить оптимальный маршрут, например доставка еды, самостоятельное вождение и т. д. Человеческому глазу сложно сделать оптимальный выбор, ведь по таким факторам, как дорожные условия, вообще невозможно судить. Здесь необходимо использовать алгоритмы для выбора наилучшего маршрута. Это также главный герой этой статьи: алгоритм Дейкстры.

Алгоритм Дейкстры

Алгоритм Дейкстры (также переводится как Дейкстра) был предложен в 1956 году голландским ученым-компьютерщиком Айжером Дейкстрой. Поиск в ширину используется для решения задачи поиска кратчайшего пути с одним источником для взвешенных ориентированных графов. Сгенерируйте дерево кратчайших путей, взяв вершину в качестве исходного узла, а затем найдя кратчайший путь от этой вершины ко всем другим узлам в графе.

Шаги алгоритма Дейкстры

1. Отметьте выбранную начальную вершину, текущее расстояние равно 0, а остальные вершины установлены на бесконечность.
2. Установите непосещенную вершину с наименьшим текущим расстоянием в качестве текущей вершины C.
3. Для каждой соседней вершины N текущей вершины C: добавить текущее расстояние C к весу ребра, соединяющего C—N. Если оно меньше текущего расстояния вершины N, установите его равным новому текущему расстоянию N.
4. Отметить текущую вершину C как посещенную.
5. Если есть непосещенные вершины, повторяйте шаг 2, пока не будут посещены все вершины.

Временная сложность алгоритма Дейкстры

Предположим, у нас есть V для количества вершин в графе и E для количества ребер в графе.

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

Если список смежности + двоичная куча используется в качестве приоритетной очереди для поиска наименьшей вершины, то время, необходимое для алгоритма, равно.

Если использование списка смежности + кучи Фибоначчи может немного улучшить производительность, дайте алгоритму время работы до.

Пример алгоритма Дейкстры

Алгоритм Дейкстры используется для вычисления кратчайшего пути между вершиной (начальной точкой) и каждой другой вершиной графа.

Поиск кратчайших путей между вершиной C и другими вершинами графа.

Сначала нам нужно инициализировать данные, выбрать вершину C в качестве начальной вершины, текущее расстояние равно 0, а для остальных вершин, поскольку мы не знаем минимального расстояния, оно начинается с бесконечности.

Вершины, смежные с C, теперь A, B, D, и, поскольку нет определенного порядка, мы решили начать с A. Поскольку вес от C до A равен 1, минимальное расстояние между текущей вершиной и весом C-A меньше бесконечности по умолчанию, поэтому минимальное расстояние от C-A равно 0+1=1.

Поскольку вес от C до B равен 7, минимальное расстояние между текущей вершиной и весом C-B меньше бесконечности по умолчанию, поэтому минимальное расстояние от C-B равно 0+7=7.

Поскольку вес от C до D равен 2, минимальное расстояние между текущей вершиной и весом C-D меньше бесконечности по умолчанию, поэтому минимальное расстояние от C-D равно 0+2=2.
В это время кратчайшее расстояние C-A равно 1;
Кратчайшее расстояние между C-B равно 7;
Кратчайшее расстояние между C-D равно 2.

Выберите следующую текущую вершину как A. Поскольку вес от A до B равен 3, минимальное расстояние между текущей вершиной и весом A-B меньше 7, поэтому минимальное расстояние от C-B равно 1+3=4.
Текущие кратчайшие пути — C-A, C-A-B и C-D соответственно.

Выберите следующую текущую вершину как D. Поскольку вес от D до E равен 7, минимальное расстояние между текущей вершиной и весом D-E меньше бесконечности, поэтому минимальное расстояние от C-E равно 2+7=9.
В это время вес D-B равен 5, а минимальное расстояние C-B равно 2+5=7, что больше, чем текущее минимальное расстояние, поэтому нет необходимости обновлять расстояние C-B.
Текущие кратчайшие пути: C-A, C-A-B, C-D, C-D-E.

Выберите следующую текущую вершину как B. Поскольку вес от B до E равен 1, минимальное расстояние между текущей вершиной и весом от B до E меньше 9, поэтому минимальное расстояние от C до E равно 4+1=5. Теперь кратчайшее расстояние для обновления C—E равно 5, и все вершины сделаны с маркерами.

Наконец, самые короткие расстояния: C—A=1, C—B=4, C—D=2 и C—E=5.
Кратчайшие пути: C-A, C-A-B, C-D, C-A-B-E.

Суммировать

Алгоритм Дейкстры использует поиск в ширину для решения задачи поиска кратчайшего пути с одним источником с помощью взвешенного ориентированного графа. Передайте вершину как исходный узел, а затем найдите кратчайший путь от этой вершины ко всем другим вершинам графа.

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

Однако за счет оптимизации структуры хранения при использовании двоичной кучи или кучи Фибоначчи для хранения эффективность в определенной степени повышается.

PS:
Чистые горы и чистые воды начинаются с пыли, а знания ценнее усердия.
У меня есть вино, у тебя есть история?
Публичный аккаунт WeChat: "болтать".
Добро пожаловать в чат и поговорим о коде.