Рубрики

Алгоритм Дейкстры для представления списка смежности | Жадный Алго-8

Мы рекомендуем прочитать следующие два сообщения в качестве предварительного условия этого сообщения.

1. Жадные алгоритмы | Набор 7 (алгоритм кратчайшего пути Дейкстры)
2. Граф и его представления

Мы обсудили алгоритм Дейкстры и его реализацию для матричного представления графов смежности . Временная сложность для матричного представления составляет O (V ^ 2). В этом посте обсуждается алгоритм O (ELogV) для представления списка смежности.

Как обсуждалось в предыдущем посте, в алгоритме Дейкстры поддерживаются два набора, один набор содержит список вершин, уже включенных в SPT (Дерево кратчайших путей), другой набор содержит еще не включенные вершины. С представлением списка смежности все вершины графа могут быть пройдены за O (V + E) время с использованием BFS . Идея состоит в том, чтобы обойти все вершины графа с использованием BFS и использовать Min Heap для хранения вершин, еще не включенных в SPT (или вершин, для которых кратчайшее расстояние еще не завершено). Min Heap используется в качестве приоритетной очереди для получения вершины минимального расстояния из набора еще не включенных вершин. Временная сложность операций, таких как extract-min и значение ключа уменьшения, составляет O (LogV) для Min Heap.

Ниже приведены подробные шаги.
1) Создайте Min Heap размера V, где V — количество вершин в данном графе. Каждый узел минимальной кучи содержит номер вершины и значение расстояния вершины.
2) Инициализируйте Min Heap с исходной вершиной в качестве корня (значение расстояния, назначенное исходной вершине, равно 0). Значение расстояния, присвоенное всем остальным вершинам, равно INF (бесконечно).
3) Пока Min Heap не пусто, сделайте следующее
… .. a) Извлечь вершину с минимальным значением расстояния до узла из Min Heap. Пусть извлеченная вершина будет u.
… .. б) Для каждой смежной вершины v из u, проверьте, находится ли v в Min Heap. Если v находится в Min Heap и значение расстояния больше, чем вес uv плюс значение расстояния u, то обновите значение расстояния v.

Давайте разберемся со следующим примером. Пусть заданная исходная вершина будет 0

Первоначально значение расстояния исходной вершины равно 0 и INF (бесконечно) для всех остальных вершин. Таким образом, исходная вершина извлекается из Min Heap, а значения расстояний вершин, смежных с 0 (1 и 7), обновляются. Min Heap содержит все вершины, кроме вершины 0.
Вершины, выделенные зеленым цветом, — это вершины, для которых минимальные расстояния определены и не указаны в Min Heap

Поскольку значение расстояния вершины 1 является минимальным среди всех узлов в Min Heap, оно извлекается из Min Heap, а значения расстояния для вершин, смежных с 1, обновляются (расстояние обновляется, если вершина не находится в Min Heap, а расстояние до 1 короче чем предыдущее расстояние). Min Heap содержит все вершины, кроме вершин 0 и 1.

Выберите вершину с минимальным значением расстояния из минимальной кучи. Вершина 7 выбрана. Таким образом, min heap теперь содержит все вершины, кроме 0, 1 и 7. Обновите значения расстояний смежных вершин, равных 7. Значение расстояния вершин 6 и 8 становится конечным (15 и 9 соответственно).

Выберите вершину с минимальным расстоянием от минимальной кучи. Вершина 6 выбрана. Таким образом, min heap теперь содержит все вершины, кроме 0, 1, 7 и 6. Обновите значения расстояния смежных вершин из 6. Обновлены значения расстояния вершин 5 и 8.

Вышеуказанные шаги повторяются до тех пор, пока минимальная куча не станет пустой. Наконец, мы получаем следующее дерево кратчайшего пути.

C ++

// C / C ++ программа для алгоритма кратчайшего пути Дейкстры для смежности
// список представлений графа

  
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

  
// Структура для представления узла в списке смежности

struct AdjListNode

{

    int dest;

    int weight;

    struct AdjListNode* next;

};

  
// Структура для представления списка смежности

struct AdjList

{

    struct AdjListNode *head;  // указатель на головной узел списка

};

  
// Структура для представления графа. Граф - это массив списков смежности.
// Размер массива будет V (количество вершин в графе)

struct Graph

{

    int V;

    struct AdjList* array;

};

  
// Служебная функция для создания нового узла списка смежности

struct AdjListNode* newAdjListNode(int dest, int weight)

{

    struct AdjListNode* newNode =

            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));

    newNode->dest = dest;

    newNode->weight = weight;

    newNode->next = NULL;

    return newNode;

}

  
// Вспомогательная функция, которая создает граф из V вершин

struct Graph* createGraph(int V)

{

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

    graph->V = V;

  

    // Создать массив списков смежности. Размер массива будет V

    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

  

     // Инициализируем каждый список смежности как пустой, сделав head как NULL

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

        graph->array[i].head = NULL;

  

    return graph;

}

  
// Добавляем ребро в неориентированный граф

void addEdge(struct Graph* graph, int src, int dest, int weight)

{

    // Добавить ребро из src в dest. Новый узел добавляется в смежность

    // список источников Узел добавляется в начале

    struct AdjListNode* newNode = newAdjListNode(dest, weight);

    newNode->next = graph->array[src].head;

    graph->array[src].head = newNode;

  

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

    newNode = newAdjListNode(src, weight);

    newNode->next = graph->array[dest].head;

    graph->array[dest].head = newNode;

}

  
// Структура для представления узла минимальной кучи

struct MinHeapNode

{

    int  v;

    int dist;

};

  
// Структура для представления кучи мин

struct MinHeap

{

    int size;      // Количество узлов кучи, присутствующих в данный момент

    int capacity;  // Емкость мин кучи

    int *pos;     // Это необходимо для lowerKey ()

    struct MinHeapNode **array;

};

  
// Вспомогательная функция для создания нового узла Min Heap

struct MinHeapNode* newMinHeapNode(int v, int dist)

{

    struct MinHeapNode* minHeapNode =

           (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));

    minHeapNode->v = v;

    minHeapNode->dist = dist;

    return minHeapNode;

}

  
// Утилита для создания Min Heap

struct MinHeap* createMinHeap(int capacity)

{

    struct MinHeap* minHeap =

         (struct MinHeap*) malloc(sizeof(struct MinHeap));

    minHeap->pos = (int *)malloc(capacity * sizeof(int));

    minHeap->size = 0;

    minHeap->capacity = capacity;

    minHeap->array =

         (struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*));

    return minHeap;

}

  
// Вспомогательная функция для замены двух узлов минимальной кучи. Требуется в течение минуты heapify

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)

{

    struct MinHeapNode* t = *a;

    *a = *b;

    *b = t;

}

  
// Стандартная функция для работы с данным idx
// Эта функция также обновляет положение узлов, когда они меняются местами.
// Позиция нужна для lowerKey ()

void minHeapify(struct MinHeap* minHeap, int idx)

{

    int smallest, left, right;

    smallest = idx;

    left = 2 * idx + 1;

    right = 2 * idx + 2;

  

    if (left < minHeap->size &&

        minHeap->array[left]->dist < minHeap->array[smallest]->dist )

      smallest = left;

  

    if (right < minHeap->size &&

        minHeap->array[right]->dist < minHeap->array[smallest]->dist )

      smallest = right;

  

    if (smallest != idx)

    {

        // Узлы, которые нужно поменять местами в минимальной куче

        MinHeapNode *smallestNode = minHeap->array[smallest];

        MinHeapNode *idxNode = minHeap->array[idx];

  

        // Меняем местами

        minHeap->pos[smallestNode->v] = idx;

        minHeap->pos[idxNode->v] = smallest;

  

        // Переставляем узлы

        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);

  

        minHeapify(minHeap, smallest);

    }

}

  
// Утилита для проверки, является ли данный minHeap пустым или нет

int isEmpty(struct MinHeap* minHeap)

{

    return minHeap->size == 0;

}

  
// Стандартная функция для извлечения минимального узла из кучи

struct MinHeapNode* extractMin(struct MinHeap* minHeap)

{

    if (isEmpty(minHeap))

        return NULL;

  

    // Сохраняем корневой узел

    struct MinHeapNode* root = minHeap->array[0];

  

    // Заменить корневой узел последним узлом

    struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];

    minHeap->array[0] = lastNode;

  

    // Обновляем позицию последнего узла

    minHeap->pos[root->v] = minHeap->size-1;

    minHeap->pos[lastNode->v] = 0;

  

    // Уменьшаем размер кучи и корнем корнем

    --minHeap->size;

    minHeapify(minHeap, 0);

  

    return root;

}

  
// Функция для уменьшения значения dist данной вершины v. Эта функция
// использует pos [] из min heap, чтобы получить текущий индекс узла в min heap

void decreaseKey(struct MinHeap* minHeap, int v, int dist)

{

    // Получить индекс v в массиве кучи

    int i = minHeap->pos[v];

  

    // Получить узел и обновить его значение dist

    minHeap->array[i]->dist = dist;

  

    // Подниматься вверх, пока целое дерево не печетно.

    // Это цикл O (Logn)

    while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist)

    {

        // Поменяем местами этот узел

        minHeap->pos[minHeap->array[i]->v] = (i-1)/2;

        minHeap->pos[minHeap->array[(i-1)/2]->v] = i;

        swapMinHeapNode(&minHeap->array[i],  &minHeap->array[(i - 1) / 2]);

  

        // перейти к родительскому индексу

        i = (i - 1) / 2;

    }

}

  
// Полезная функция, чтобы проверить, является ли данная вершина
// 'v' в минимальной куче или нет

bool isInMinHeap(struct MinHeap *minHeap, int v)

{

   if (minHeap->pos[v] < minHeap->size)

     return true;

   return false;

}

  
// Утилита, используемая для печати решения

void printArr(int dist[], int n)

{

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

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

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

}

  
// Основная функция, которая вычисляет расстояния по кратчайшим путям от src до всех
// вершины. Это функция O (ELogV)

void dijkstra(struct Graph* graph, int src)

{

    int V = graph->V;// Получить количество вершин в графе

    int dist[V];      // значения dist, используемые для выбора минимального края веса в разрезе

  

    // minHeap представляет множество E

    struct MinHeap* minHeap = createMinHeap(V);

  

    // Инициализируем минимальную кучу со всеми вершинами. значение dist всех вершин

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

    {

        dist[v] = INT_MAX;

        minHeap->array[v] = newMinHeapNode(v, dist[v]);

        minHeap->pos[v] = v;

    }

  

    // Сделать значение dist вершины src равным 0, чтобы оно извлекалось первым

    minHeap->array[src] = newMinHeapNode(src, dist[src]);

    minHeap->pos[src]   = src;

    dist[src] = 0;

    decreaseKey(minHeap, src, dist[src]);

  

    // изначально размер min heap равен V

    minHeap->size = V;

  

    // В цикле followin min heap содержит все узлы

    // кратчайшее расстояние которого еще не определено.

    while (!isEmpty(minHeap))

    {

        // Извлекаем вершину с минимальным значением расстояния

        struct MinHeapNode* minHeapNode = extractMin(minHeap);

        int u = minHeapNode->v; // Сохраняем извлеченный номер вершины

  

        // Обход всех смежных вершин u (извлеченный

        // вершина) и обновить их значения расстояния

        struct AdjListNode* pCrawl = graph->array[u].head;

        while (pCrawl != NULL)

        {

            int v = pCrawl->dest;

  

            // Если кратчайшее расстояние до v еще не определено, а расстояние до v

            // через u меньше предварительно рассчитанного расстояния

            if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX && 

                                          pCrawl->weight + dist[u] < dist[v])

            {

                dist[v] = dist[u] + pCrawl->weight;

  

                // обновить значение расстояния в мин куче

                decreaseKey(minHeap, v, dist[v]);

            }

            pCrawl = pCrawl->next;

        }

    }

  

    // выводим рассчитанные кратчайшие расстояния

    printArr(dist, V);

}

  

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

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

    int V = 9;

    struct Graph* graph = createGraph(V);

    addEdge(graph, 0, 1, 4);

    addEdge(graph, 0, 7, 8);

    addEdge(graph, 1, 2, 8);

    addEdge(graph, 1, 7, 11);

    addEdge(graph, 2, 3, 7);

    addEdge(graph, 2, 8, 2);

    addEdge(graph, 2, 5, 4);

    addEdge(graph, 3, 4, 9);

    addEdge(graph, 3, 5, 14);

    addEdge(graph, 4, 5, 10);

    addEdge(graph, 5, 6, 2);

    addEdge(graph, 6, 7, 1);

    addEdge(graph, 6, 8, 6);

    addEdge(graph, 7, 8, 7);

  

    dijkstra(graph, 0);

  

    return 0;

}

питон

# Программа на Python для самой короткой Дейкстры
# алгоритм пути для смежности
# список представления графа

  

from collections import defaultdict

import sys

  

class Heap():

  

    def __init__(self):

        self.array = []

        self.size = 0

        self.pos = []

  

    def newMinHeapNode(self, v, dist):

        minHeapNode = [v, dist]

        return minHeapNode

  

    # Утилита для замены двух узлов

    # мин кучи. Требуется в течение минуты heapify

    def swapMinHeapNode(self,a, b):

        t = self.array[a]

        self.array[a] = self.array[b]

        self.array[b] = t

  

    # Стандартная функция для кучи на заданном idx

    # Эта функция также обновляет положение узлов

    # когда они поменялись местами. Нужна позиция

    # для lowerKey ()

    def minHeapify(self, idx):

        smallest = idx

        left = 2*idx + 1

        right = 2*idx + 2

  

        if left < self.size and self.array[left][1] \

                                < self.array[smallest][1]:

            smallest = left

  

        if right < self.size and self.array[right][1]\

                                < self.array[smallest][1]:

            smallest = right

  

        # Узлы, которые должны быть заменены в мин.

        # куча, если idx не самый маленький

        if smallest != idx:

  

            # Поменять позиции

            self.pos[ self.array[smallest][0] ] = idx

            self.pos[ self.array[idx][0] ] = smallest

  

            # Перестановка узлов

            self.swapMinHeapNode(smallest, idx)

  

            self.minHeapify(smallest)

  

    # Стандартная функция для извлечения минимума

    # узел из кучи

    def extractMin(self):

  

        # Вернуть NULL, если куча пуста

        if self.isEmpty() == True:

            return

  

        # Хранить корневой узел

        root = self.array[0]

  

        # Заменить корневой узел последним узлом

        lastNode = self.array[self.size - 1]

        self.array[0] = lastNode

  

        # Обновить позицию последнего узла

        self.pos[lastNode[0]] = 0

        self.pos[root[0]] = self.size - 1

  

        # Уменьшить размер кучи и укрупнить корень

        self.size -= 1

        self.minHeapify(0)

  

        return root

  

    def isEmpty(self):

        return True if self.size == 0 else False

  

    def decreaseKey(self, v, dist):

  

        # Получить индекс v в массиве кучи

  

        i = self.pos[v]

  

        # Получить узел и обновить его значение dist

        self.array[i][1] = dist

  

        # Путешествуйте, пока полное дерево

        # не печалился. Это цикл O (Logn)

        while i > 0 and self.array[i][1] < self.array[(i - 1) / 2][1]:

  

            # Поменяйте местами этот узел с его родителем

            self.pos[ self.array[i][0] ] = (i-1)/2

            self.pos[ self.array[(i-1)/2][0] ] = i

            self.swapMinHeapNode(i, (i - 1)/2 )

  

            # перейти к родительскому индексу

            i = (i - 1) / 2;

  

    # Функция полезности для проверки, если данный

    # вершина 'v' находится в минимальной куче или нет

    def isInMinHeap(self, v):

  

        if self.pos[v] < self.size:

            return True

        return False

  

  

def printArr(dist, n):

    print "Vertex\tDistance from source"

    for i in range(n):

        print "%d\t\t%d" % (i,dist[i])

  

  

class Graph():

  

    def __init__(self, V):

        self.V = V

        self.graph = defaultdict(list)

  

    # Добавляет ребро в неориентированный граф

    def addEdge(self, src, dest, weight):

  

        # Добавить ребро из src в dest. Новый узел

        # добавлен в список смежности src.

        # узел добавлен в начале. Первый

        # элемент узла имеет место назначения

        # а второй элемент имеет вес

        newNode = [dest, weight]

        self.graph[src].insert(0, newNode)

  

        # Так как график не направлен, добавьте ребро

        # от Dest до SRC также

        newNode = [src, weight]

        self.graph[dest].insert(0, newNode)

  

    # Основная функция, которая вычисляет расстояния

    # кратчайших путей от src до всех вершин.

    # Это функция O (ELogV)

    def dijkstra(self, src):

  

        V = self.V  # Получить количество вершин в графе

        dist = []   # значения dist используются для выбора минимума

                    # край веса в разрезе

  

        # minHeap представляет множество E

        minHeap = Heap()

  

        # Инициализировать минимальную кучу со всеми вершинами.

        # dist значение всех вершин

        for v in range(V):

            dist.append(sys.maxint)

            minHeap.array.append( minHeap.newMinHeapNode(v, dist[v]) )

            minHeap.pos.append(v)

  

        # Сделать значение dist вершины src равным 0, чтобы

        # что он извлекается первым

        minHeap.pos[src] = src

        dist[src] = 0

        minHeap.decreaseKey(src, dist[src])

  

        # Первоначально размер min heap равен V

        minHeap.size = V;

  

        # В следующем цикле min heap содержит все узлы

        # кратчайшее расстояние которого еще не определено.

        while minHeap.isEmpty() == False:

  

            # Извлечь вершину с минимальным значением расстояния

            newHeapNode = minHeap.extractMin()

            u = newHeapNode[0]

  

            # Пройдите через все смежные вершины

            # u (извлеченная вершина) и обновить их

            # значения расстояния

            for pCrawl in self.graph[u]:

  

                v = pCrawl[0]

  

                # Если кратчайшее расстояние до v не завершено

                # пока нет, а расстояние до v через u меньше

                # чем его ранее рассчитанное расстояние

                if minHeap.isInMinHeap(v) and dist[u] != sys.maxint and \

                   pCrawl[1] + dist[u] < dist[v]:

                        dist[v] = pCrawl[1] + dist[u]

  

                        # обновить значение расстояния

                        # в мин кучу также

                        minHeap.decreaseKey(v, dist[v])

  

        printArr(dist,V)

  

  
# Драйвер программы для проверки вышеуказанных функций

graph = Graph(9)

graph.addEdge(0, 1, 4)

graph.addEdge(0, 7, 8)

graph.addEdge(1, 2, 8)

graph.addEdge(1, 7, 11)

graph.addEdge(2, 3, 7)

graph.addEdge(2, 8, 2)

graph.addEdge(2, 5, 4)

graph.addEdge(3, 4, 9)

graph.addEdge(3, 5, 14)

graph.addEdge(4, 5, 10)

graph.addEdge(5, 6, 2)

graph.addEdge(6, 7, 1)

graph.addEdge(6, 8, 6)

graph.addEdge(7, 8, 7)

graph.dijkstra(0)

  
# Этот код предоставлен Divyanshu Mehta


Выход:

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

Сложность времени: временная сложность приведенного выше кода / алгоритма выглядит как O (V ^ 2), так как есть два вложенных цикла while. Если мы посмотрим поближе, то заметим, что операторы во внутреннем цикле выполняются O (V + E) раз (аналогично BFS). Во внутреннем цикле есть операция lowerKey (), которая занимает время O (LogV). Таким образом, общая сложность времени составляет O (E + V) * O (LogV), которая равна O ((E + V) * LogV) = O (ELogV)
Обратите внимание, что приведенный выше код использует двоичную кучу для реализации очереди приоритетов. Временная сложность может быть уменьшена до O (E + VLogV) с помощью кучи Фибоначчи. Причина в том, что Fibonacci Heap занимает O (1) время для операции уменьшения ключа, в то время как Binary Heap занимает O (Logn) время.

Примечания:
1) Код вычисляет кратчайшее расстояние, но не вычисляет информацию о пути. Мы можем создать родительский массив, обновить родительский массив при обновлении расстояния (как реализация prim ) и использовать его, чтобы показать кратчайший путь от источника к различным вершинам.

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

3) Код находит кратчайшие расстояния от источника до всех вершин. Если нас интересует только кратчайшее расстояние от источника до единственной цели, мы можем разорвать цикл for, когда выбранная вершина минимального расстояния равна цели (шаг 3.a алгоритма).

4) Алгоритм Дейкстры не работает для графов с отрицательными весовыми ребрами. Для графиков с отрицательными весовыми гранями можно использовать алгоритм Беллмана – Форда , который мы вскоре обсудим в отдельном посте.

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

Ссылки:
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.
Алгоритмы Санджоя Дасгупты, Христоса Пападимитриу, Умеша Вазирани

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

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

Алгоритм Дейкстры для представления списка смежности | Жадный Алго-8

0.00 (0%) 0 votes