Рубрики

Алгоритм кратчайшего пути Дейкстры с использованием набора в STL

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



Input : Source = 0
Output : 
     Vertex   Distance from Source
        0                0
        1                4
        2                12
        3                19
        4                21
        5                11
        6                9
        7                8
        8                14

Мы обсудили кратчайшие пути реализации Дейкстры.

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

  • ExtractMin: из всех тех вершин, кратчайшее расстояние которых еще не найдено, нам нужно получить вершину с минимальным расстоянием.
  • DecreaseKey: после извлечения вершины нам нужно обновить расстояние до соседних вершин, а если новое расстояние меньше, обновить это в структуре данных.

Вышеуказанные операции могут быть легко реализованы с помощью структуры данных set в C ++ STL , set хранит все свои ключи в отсортированном порядке, поэтому минимальная удаленная вершина всегда будет в начале, мы можем извлечь ее оттуда, что является операцией ExtractMin, и соответствующим образом обновить другую смежную вершину. если расстояние какого-либо из вексев стало меньше, удалите его предыдущую запись и вставьте новую обновленную запись, которая является операцией DecreaseKey.

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

1) Initialize distances of all vertices as infinite.

2) Create an empty set.  Every item of set is a pair
  (weight, vertex). Weight (or distance) is used used
  as first item  of pair as first item is by default 
  used to compare two pairs.

3) Insert source vertex into the set and make its
   distance as 0.

4) While Set doesn't become empty, do following
    a) Extract minimum distance vertex from Set. 
       Let the extracted vertex be u.
    b) Loop through all adjacent of u and do 
       following for every vertex v.

           // If there is a shorter path to v
           // through u. 
           If dist[v] > dist[u] + weight(u, v)

               (i) Update distance of v, i.e., do
                     dist[v] = dist[u] + weight(u, v)
               (i) If v is in set, update its distance
                   in set by removing it first, then
                   inserting with new distance
               (ii) If v is not in set, then insert
                    it in set with new distance
               
5) Print distance array dist[] to print all shortest
   paths. 

Ниже приведена реализация вышеуказанной идеи на C ++.

// Программа для поиска кратчайшего пути Дейкстры с использованием набора STL
#include<bits/stdc++.h>

using namespace std;

# define INF 0x3f3f3f3f

  
// Этот класс представляет ориентированный граф, используя
// представление списка смежности

class Graph

{

    int V;    // Количество вершин

  

    // В взвешенном графе нам нужно хранить вершину

    // и весовая пара для каждого ребра

    list< pair<int, int> > *adj;

  

public:

    Graph(int V);  // Конструктор

  

    // функция для добавления ребра на график

    void addEdge(int u, int v, int w);

  

    // печатает кратчайший путь из s

    void shortestPath(int s);

};

  
// Распределяет память для списка смежности

Graph::Graph(int V)

{

    this->V = V;

    adj = new list< pair<int, int> >[V];

}

  

void Graph::addEdge(int u, int v, int w)

{

    adj[u].push_back(make_pair(v, w));

    adj[v].push_back(make_pair(u, w));

}

  
// Печатает кратчайшие пути из src во все остальные вершины

void Graph::shortestPath(int src)

{

    // Создать набор для хранения вершин, которые

    // предварительно обработанный

    set< pair<int, int> > setds;

  

    // Создать вектор для расстояний и инициализировать все

    // расстояния как бесконечные (INF)

    vector<int> dist(V, INF);

  

    // Вставляем сам источник в Set и инициализируем его

    // расстояние как 0.

    setds.insert(make_pair(0, src));

    dist[src] = 0;

  

    / * Цикл пока все кратчайшие расстояния не будут завершены

       тогда setds станет пустым * /

    while (!setds.empty())

    {

        // Первая вершина в Set - это минимальное расстояние

        // вершина, извлечь ее из множества.

        pair<int, int> tmp = *(setds.begin());

        setds.erase(setds.begin());

  

        // метка вершины хранится во второй из пары

        // нужно сделать так, чтобы сохранить вершины

        // отсортированное расстояние (расстояние должно быть первым элементом

        // в паре)

        int u = tmp.second;

  

        // 'i' используется для получения всех смежных вершин вершины

        list< pair<int, int> >::iterator i;

        for (i = adj[u].begin(); i != adj[u].end(); ++i)

        {

            // Получить метку вершины и вес текущего смежного

            // из вас.

            int v = (*i).first;

            int weight = (*i).second;

  

            // Если есть короткий путь к v через u.

            if (dist[v] > dist[u] + weight)

            {

                / * Если расстояние от v не до INF, оно должно быть в

                    наш набор, так что удалив его и вставив снова

                    с обновленным меньшим расстоянием.

                    Примечание: мы извлекаем только те вершины из множества

                    для которого расстояние является окончательным. Так что для них,

                    мы бы никогда не добрались сюда. * /

                if (dist[v] != INF)

                    setds.erase(setds.find(make_pair(dist[v], v)));

  

                // Обновление расстояния v

                dist[v] = dist[u] + weight;

                setds.insert(make_pair(dist[v], v));

            }

        }

    }

  

    // Печатать кратчайшие расстояния, хранящиеся в dist []

    printf("Vertex   Distance from Source\n");

    for (int i = 0; i < V; ++i)

        printf("%d \t\t %d\n", i, dist[i]);

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    // создаем график, приведенный выше

    int V = 9;

    Graph g(V);

  

    // делаем выше показанный график

    g.addEdge(0, 1, 4);

    g.addEdge(0, 7, 8);

    g.addEdge(1, 2, 8);

    g.addEdge(1, 7, 11);

    g.addEdge(2, 3, 7);

    g.addEdge(2, 8, 2);

    g.addEdge(2, 5, 4);

    g.addEdge(3, 4, 9);

    g.addEdge(3, 5, 14);

    g.addEdge(4, 5, 10);

    g.addEdge(5, 6, 2);

    g.addEdge(6, 7, 1);

    g.addEdge(6, 8, 6);

    g.addEdge(7, 8, 7);

  

    g.shortestPath(0);

  

    return 0;

}

Выход :

Vertex   Distance from Source
0 		 0
1 		 4
2 		 12
3 		 19
4 		 21
5 		 11
6 		 9
7 		 8
8 		 14

Сложность времени: Набор в C ++ обычно реализуется с использованием самобалансирующихся бинарных деревьев поиска. Следовательно, временная сложность операций набора, таких как вставка, удаление, является логарифмической, а временная сложность вышеуказанного решения — O (ELogV)).

Алгоритм кратчайшего пути Дейкстры, использующий приоритетную очередь STL

Эта статья предоставлена Уткаршем Триведи . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм кратчайшего пути Дейкстры с использованием набора в STL

0.00 (0%) 0 votes