Рубрики

Алгоритм набора (Оптимизированный Дейкстра для малых весовых коэффициентов)

Алгоритм кратчайшего пути Дейкстры выполняется за время O (Elog V), когда реализован с представлением списка смежности (подробности см. В реализациях на C и C ++ на основе STL ).



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

Можем ли мы оптимизировать алгоритм кратчайшего пути Дейкстры, чтобы он работал лучше, чем O (E log V), если максимальный вес мал (или диапазон весов ребер мал)?
Например, на приведенной выше диаграмме максимальный вес равен 14. Во многих случаях диапазон весов на ребрах находится в небольшом диапазоне (т. Е. Весь вес ребер может быть сопоставлен с 0, 1, 2 … w, где w — небольшое число ). В этом случае алгоритм Дейкстры может быть изменен с использованием другой структуры данных, сегментов, которая называется циферблатной реализацией алгоритма Дейкстры. временная сложность равна O (E + WV), где W — максимальный вес на любом ребре графа, поэтому мы можем видеть, что если W мало, то эта реализация выполняется намного быстрее, чем традиционный алгоритм. Ниже приведены важные замечания.

  • Максимальное расстояние между любыми двумя узлами может быть при максимальном w (V — 1) (w — максимальный вес ребра, и мы можем иметь при максимальных V-1 ребрах между двумя вершинами).
  • В алгоритме Дейкстры расстояния финализируются в неубывающих, т. Е. Расстояние до ближайших (к данному источнику) вершин завершается до удаленных вершин.

Алгоритм

Ниже приведен полный алгоритм:

  1. Поддерживает некоторые ведра, пронумерованные 0, 1, 2,…, wV.
  2. Ведро k содержит все временно помеченные узлы с расстоянием, равным k.
  3. Узлы в каждом сегменте представлены списком вершин.
  4. Контейнеры 0, 1, 2, .. wV проверяются последовательно до тех пор, пока не будет найден первый непустой сегмент. Каждый узел, содержащийся в первом непустом сегменте, имеет метку минимального расстояния по определению.
  5. Один за другим эти узлы с меткой минимального расстояния навсегда помечаются и удаляются из корзины во время процесса сканирования.
  6. Таким образом, операции с участием вершины включают в себя:
    • Проверка пустого ведра
    • Добавление вершины в ведро
    • Удаление вершины из ведра.
  7. Положение временно помеченной вершины в сегментах обновляется соответствующим образом при изменении метки расстояния вершины.
  8. Процесс повторяется до тех пор, пока все вершины не будут помечены навсегда (или расстояния всех вершин не будут определены).

Реализация

Поскольку максимальное расстояние может быть w (V — 1), мы создаем wV-сегменты (больше для простоты кода) для реализации алгоритма, который может быть большим, если w большое.

// C ++ Программа для реализации набора Дейкстры
#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, int W);

};

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

Graph::Graph(int V)

{

    this->V = V;

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

}

  
// добавляет ребро между u и v веса w

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 во все остальные вершины.
// W - максимальный вес ребра

void Graph::shortestPath(int src, int W)

{

    / * С каждым расстоянием, итератор к этой вершине в

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

       в O (1) во время обновления. Так

    dist [i] .first = расстояние i-й вершины от вершины src

    dits [i] .second = итератор для вершины i в номере корзины * /

    vector<pair<int, list<int>::iterator> > dist(V);

  

    // Инициализируем все расстояния как бесконечные (INF)

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

        dist[i].first = INF;

  

    // Создать ведра B [].

    // B [i] сохраняем вершину метки расстояния i

    list<int> B[W * V + 1];

  

    B[0].push_back(src);

    dist[src].first = 0;

  

    //

    int idx = 0;

    while (1)

    {

        // Пройдем последовательно ведра до одного непустого

        // ведро найдено

        while (B[idx].size() == 0 && idx < W*V)

            idx++;

  

        // Если все ведра пусты, мы закончили.

        if (idx == W * V)

            break;

  

        // Взять верхнюю вершину из ведра и вытолкнуть ее

        int u = B[idx].front();

        B[idx].pop_front();

  

        // Обрабатываем все смежные области извлеченной вершины 'u' и

        // обновить их дистанционно, если требуется.

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

        {

            int v = (*i).first;

            int weight = (*i).second;

  

            int du = dist[u].first;

            int dv = dist[v].first;

  

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

            if (dv > du + weight)

            {

                // Если dv не INF, то он должен быть в B [dv]

                // ведро, поэтому удалите запись, используя итератор

                // в O (1)

                if (dv != INF)

                    B[dv].erase(dist[v].second);

  

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

                dist[v].first = du + weight;

                dv = dist[v].first;

  

                // толкаем вершину v в область обновленного расстояния

                B[dv].push_front(v);

  

                // сохраняем обновленный итератор в dist [v] .second

                dist[v].second = B[dv].begin();

            }

        }

    }

  

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

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

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

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

}

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

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);

  

    // максимальное взвешенное ребро - 14

    g.shortestPath(0, 14);

  

    return 0;

}

Выход:

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

иллюстрация

Ниже шаг за шагом иллюстрации взяты из здесь .

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

Алгоритм набора (Оптимизированный Дейкстра для малых весовых коэффициентов)

0.00 (0%) 0 votes