Алгоритм Dijkstras также известен как алгоритм поиска кратчайшего пути. Это процедура поиска кратчайшего пути между узлами/ребрами графа. Кратчайший граф дерева создается путем перехода от исходной вершины ко всем остальным точкам графа.
Алгоритм
- Перед непосредственной реализацией графа Dijkstras на языке программирования C++ нам необходимо понять работу этого графового алгоритма.
- Первым шагом является создание «sptSet», который сокращенно называется набором дерева кратчайших путей; в нем хранится запись тех вершин, которые входят в кратчайший путь. На начальном этапе этот набор объявляется как NULL.
- На следующем шаге сначала все эти значения в узлах объявляются как INFINITE, так как мы до сих пор не знаем веса путей.
- Выберите вершину «u», которой еще нет в sptSet и которая имеет минимальное значение. Затем включите его в sptSet. После этого обновите значения расстояния всех тех узлов, которые являются соседними вершинами «u». Все это делается в цикле до тех пор, пока sptSet не сможет содержать все вершины.
Реализация графового алгоритма Dijkstras
Вот реализация графа Дейкстры, где написана программа для представления матрицы смежности этого графа. Запустите программу, добавив две библиотеки, очень необходимые для выполнения программы на языке программирования C++, которые позволяют нам использовать функции cin и cout.
#include <iostream>
#include <limits.h>
После описания библиотек теперь мы предоставим размер или вершины графа, в котором нам нужен кратчайший путь. Мы дали 9 вершин, что означает, что матрица является квадратом [9] [9].
#define V 9
«V» для вершин. Поскольку для выполнения поставленной задачи алгоритм требует много шагов, каждый шаг или процесс разделен на отдельные функции для их выполнения, чтобы код был понятным и не было двусмысленности в отношении логики. Кроме того, сложность также удалена.
Здесь создана функция для поиска вершины с минимальным значением расстояния; он содержит множество вершин, не входящих в дерево, имеющее кратчайший путь. Функция будет содержать массив расстояний и sptset логического типа, набор дерева кратчайших путей и массив в качестве параметра функции. Внутри функции инициализируется минимальное значение путем объявления переменной целочисленного типа, в которой будет храниться возвращаемое значение. Вводятся две переменные, max и min_index.
Int min =INT_MAX, min_index
Здесь используется цикл for; в котором берется начальная вершина во всех вершинах, цикл будет продолжаться до тех пор, пока не будут пройдены все вершины. Условие применяется здесь с помощью оператора if, который проверяет, является ли набор кратчайших путей ложным, означает, что он пуст прямо сейчас, и расстояние вершины меньше, чем минимальное значение вершины, объявленное ранее, затем назначьте текущее значение вершины как минимальное, и min_index также будет содержать то же значение вершины.
Мин = расстояние [v], min_index = v
После того как вычислено минимальное значение вершины, следует процесс создания функции, которая будет отображать построенный ранее массив расстояний. Цикл будет перебирать каждый индекс, к которому будет осуществляться доступ и который будет отображаться. Сначала отображается номер вершины, начиная с нулевого значения, а также здесь с последовательностью упоминается расстояние вершины от источника. Эта функция объявлена здесь, но она будет вызываться позже в программе, когда весь путь будет рассчитан как кратчайшее расстояние.
Сейчас объявлена основная часть всего исходного кода, где вычисляется реализация кратчайшего пути из одного источника. Граф будет представлен представлением матрицы смежности. Эта функция принимает матрицу графика и источник в качестве значений параметров, которые будут действовать как входные данные для расчета расстояния. Сначала внутри функции мы объявим выходной массив, который будет содержать кратчайший путь от источника до определенной точки. Во-вторых, объявлен массив логических переменных, который вернет true, если вершина включена в определение кратчайшего пути в начале.
Int dist[v] ; bool sptset[v];
Все расстояния будут установлены как бесконечные, а массив кратчайшего пути дерева будет ложным. С помощью петли будет происходить весь этот процесс.
Внутри цикла вершина минимального расстояния выбирается из набора вершин, которые еще не обработаны. В первой итерации ’u’ всегда равно исходной вершине.
Int u = minDistance(расстояние, sptSet);
Те вершины, которые выбраны и пройдены, выбираются и помечаются как обработанные путем установки логической переменной в значение true.
sptSet[u] = true;
Когда добавляется одна вершина, все вершины, смежные с этой конкретной вершиной, также проверяются; это требует обновления. Таким образом, мы обновим значение «dist» смежных вершин тех вершин, которые были пикетированы до сих пор.
Внутри этого цикла for мы будем обновлять dist[v] тогда и только тогда, когда его нет в sptset, есть линия, называемая ребром от вершины u до v, и общий вес пути, который начинается с «src» к «v», проходя через «u», меньше, чем текущее значение, присутствующее в dist[v].
Dist[v] = dist[u] + graph[u][v];
После этого функция печати, которую мы объявили выше, вызывается путем передачи массива dist[] в качестве параметра.
printSolution(dist);
В основной программе мы создаем матричный граф 9*9. А затем производится вызов функции Дейкстры, через которую пропускается граф.
Сохраните весь код. Скомпилируйте код с помощью компилятора g++ в терминале Ubuntu. ’-o’ — это символ, который сохраняет вывод файла.
$ g++ -o dij dij.c
$ ./dij
Вы можете видеть, что отображаются все вершины в каждой отдельной строке вместе с расстоянием каждой вершины от источника.
Этот код помогает вычислить кратчайшее расстояние, но не поддерживает вычисление информации о пути. Этот исходный код хорош для неориентированных графов, но его можно использовать и для ориентированных графов. Используя этот код, мы можем найти кратчайшее расстояние от точки источника до всех остальных вершин графа.
Временная сложность графа Dijkstras
Мы поговорим о временной сложности реализации. Это:
0 (V^2).
Это можно уменьшить до 0 (E log V) с помощью процесса двоичной кучи. Граф Dijkstras не предназначен для графов с отрицательными весами.
Заключение
В этой статье описан процесс нахождения кратчайшего расстояния между исходным узлом и остальными узлами. К этому может быть много подходов. Но граф Дейкстры — один из лучших механизмов для этой цели. Он предназначен для неориентированных графов. Мы объяснили процесс шаг за шагом с исходным кодом, чтобы сделать его понятным для новых пользователей. Мы надеемся, что эта попытка будет оценена читателями.
