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

Дерево, Алгоритм, Tree

Содержание

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

Он отличается от минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа.

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

Алгоритм Дейкстры работает на том основании, что любой подпуть B -> D кратчайшего пути A -> D между вершинами A и D также является кратчайшим путем между вершинами B и D.

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

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

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

Проще начать с примера, а затем подумать об алгоритме.

Алгоритм Дейкстры. Псевдокод.

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

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

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

Очередь с минимальным приоритетом может использоваться для эффективного получения вершины с наименьшим расстоянием пути.

function dijkstra(G, S)
    for each vertex V in G
        distance[V] <- infinite
        previous[V] <- NULL
        If V != S, add V to Priority Queue Q
    distance[S] <- 0

    while Q IS NOT EMPTY
        U <- Extract MIN from Q
        for each unvisited neighbour V of U
            tempDistance <- distance[U] + edge_weight(U, V)
            if tempDistance < distance[V]
                distance[V] <- tempDistance
                previous[V] <- U
    return distance[], previous[]

Код для алгоритма Дейкстры

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

#include <iostream>
#include <vector>
#define INT_MAX 10000000
using namespace std;
void DijkstrasTest();
int main()
{
    DijkstrasTest();
    return 0;
}
class Node;
class Edge;
void Dijkstras();
vector<Node*>* AdjacentRemainingNodes(Node* node);
Node* ExtractSmallest(vector<Node*>& nodes);
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
void PrintShortestRouteTo(Node* destination);
vector<Node*> nodes;
vector<Edge*> edges;
class Node
{
public:
    Node(char id) 
        : id(id), previous(NULL), distanceFromStart(INT_MAX)
    {
        nodes.push_back(this);
    }
public:
    char id;
    Node* previous;
    int distanceFromStart;
};
class Edge
{
public:
    Edge(Node* node1, Node* node2, int distance) 
        : node1(node1), node2(node2), distance(distance)
    {
        edges.push_back(this);
    }
    bool Connects(Node* node1, Node* node2)
    {
        return (
            (node1 == this->node1 &&
            node2 == this->node2) ||
            (node1 == this->node2 && 
            node2 == this->node1));
    }
public:
    Node* node1;
    Node* node2;
    int distance;
};
///////////////////
void DijkstrasTest()
{
    Node* a = new Node('a');
    Node* b = new Node('b');
    Node* c = new Node('c');
    Node* d = new Node('d');
    Node* e = new Node('e');
    Node* f = new Node('f');
    Node* g = new Node('g');
    Edge* e1 = new Edge(a, c, 1);
    Edge* e2 = new Edge(a, d, 2);
    Edge* e3 = new Edge(b, c, 2);
    Edge* e4 = new Edge(c, d, 1);
    Edge* e5 = new Edge(b, f, 3);
    Edge* e6 = new Edge(c, e, 3);
    Edge* e7 = new Edge(e, f, 2);
    Edge* e8 = new Edge(d, g, 1);
    Edge* e9 = new Edge(g, f, 1);
    a->distanceFromStart = 0; // set start node
    Dijkstras();
    PrintShortestRouteTo(f);
}
///////////////////
void Dijkstras()
{
    while (nodes.size() > 0)
    {
        Node* smallest = ExtractSmallest(nodes);
        vector<Node*>* adjacentNodes = 
            AdjacentRemainingNodes(smallest);
        const int size = adjacentNodes->size();
        for (int i=0; i<size; ++i)
        {
            Node* adjacent = adjacentNodes->at(i);
            int distance = Distance(smallest, adjacent) +
                smallest->distanceFromStart;

            if (distance < adjacent->distanceFromStart)
            {
                adjacent->distanceFromStart = distance;
                adjacent->previous = smallest;
            }
        }
        delete adjacentNodes;
    }
}
// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)
{
    int size = nodes.size();
    if (size == 0) return NULL;
    int smallestPosition = 0;
    Node* smallest = nodes.at(0);
    for (int i=1; i<size; ++i)
    {
        Node* current = nodes.at(i);
        if (current->distanceFromStart <
            smallest->distanceFromStart)
        {
            smallest = current;
            smallestPosition = i;
        }
    }
    nodes.erase(nodes.begin() + smallestPosition);
    return smallest;
}
// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)
{
    vector<Node*>* adjacentNodes = new vector<Node*>();
    const int size = edges.size();
    for(int i=0; i<size; ++i)
    {
        Edge* edge = edges.at(i);
        Node* adjacent = NULL;
        if (edge->node1 == node)
        {
            adjacent = edge->node2;
        }
        else if (edge->node2 == node)
        {
            adjacent = edge->node1;
        }
        if (adjacent && Contains(nodes, adjacent))
        {
            adjacentNodes->push_back(adjacent);
        }
    }
    return adjacentNodes;
}
// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)
{
    const int size = edges.size();
    for(int i=0; i<size; ++i)
    {
        Edge* edge = edges.at(i);
        if (edge->Connects(node1, node2))
        {
            return edge->distance;
        }
    }
    return -1; // should never happen
}
// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)
{
    const int size = nodes.size();
    for(int i=0; i<size; ++i)
    {
        if (node == nodes.at(i))
        {
            return true;
        }
    }
    return false;
}
///////////////////
void PrintShortestRouteTo(Node* destination)
{
    Node* previous = destination;
    cout << "Distance from start: " 
        << destination->distanceFromStart << endl;
    while (previous)
    {
        cout << previous->id << " ";
        previous = previous->previous;
    }
    cout << endl;
}
// these two not needed
vector<Edge*>* AdjacentEdges(vector<Edge*>& Edges, Node* node);
void RemoveEdge(vector<Edge*>& Edges, Edge* edge);
vector<Edge*>* AdjacentEdges(vector<Edge*>& edges, Node* node)
{
    vector<Edge*>* adjacentEdges = new vector<Edge*>();
    const int size = edges.size();
    for(int i=0; i<size; ++i)
    {
        Edge* edge = edges.at(i);
        if (edge->node1 == node)
        {
            cout << "adjacent: " << edge->node2->id << endl;
            adjacentEdges->push_back(edge);
        }
        else if (edge->node2 == node)
        {
            cout << "adjacent: " << edge->node1->id << endl;
            adjacentEdges->push_back(edge);
        }
    }
    return adjacentEdges;
}
void RemoveEdge(vector<Edge*>& edges, Edge* edge)
{
    vector<Edge*>::iterator it;
    for (it=edges.begin(); it<edges.end(); ++it)
    {
        if (*it == edge)
        {
            edges.erase(it);
            return;
        }
    }
}

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Как стать автором?

Внесите вклад в развитие сообщества EVILEG.

Узнайте, как стать автором сайта.

Изучить
Donate

Добрый день, Дорогие Пользователи !!!

Я Евгений Легоцкой, разработчик EVILEG. И это мой хобби-проект, который помогает учиться программированию другим программистам и разработчикам

Если сайт помог вам, и вы хотите также поддержать развитие сайта, то вы можете сделать пожертвование следующими способами

PayPalYandex.Money
Timeweb

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

В течение многих лет Timeweb доказывает свою стабильность.

Для проектов на Django рекомендую VDS хостинг

Посмотреть Хостинг Timeweb
5 июня 2020 г. 23:20
Алексей

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:60баллов,
  • Очки рейтинга-1
5 июня 2020 г. 23:15
Алексей

C++ - Тест 001. Первая программа и типы данных

  • Результат:53баллов,
  • Очки рейтинга-4
V
5 июня 2020 г. 16:47
Vladzo

C++ - Тест 005. Структуры и Классы

  • Результат:83баллов,
  • Очки рейтинга4
Последние комментарии
6 июня 2020 г. 15:13
Владислав Меленчук

Как установить и настроить Django JET

Можно использовать six и оттуда импортировать unicode. Я так решил проблему) Но всё равно откатился обратно на админку джанги.
6 июня 2020 г. 11:20
BL4CK R4BBIT

Как установить и настроить Django JET

на Django >3+ работать не будет. Либо придется лезть внутрь и переопределять метод unicode . Либо писать декоратор
5 июня 2020 г. 10:52
progammist

Распознавание изображений на Python с помощью TensorFlow и Keras

Огромное спасибо за метериал, по-больше бы подобных статей (с подробным описанием работы и примерами применения) на тему современных технологий. Вопрос поразмышлять. На текущий момент реал…
5 июня 2020 г. 1:39
Евгений Легоцкой

Qt/C++ - Урок 091. Как написать кастомный делегат управляющий подсветкой строки в таблице

По-моему, смысла в этом нет особого. Если делегат будет игнорировать настройки таблицы, то это приведёт ещё к большему непониманию, что вообще происходит, для программиста, который после вас буд…
5 июня 2020 г. 1:34
IscanderChe

Qt/C++ - Урок 091. Как написать кастомный делегат управляющий подсветкой строки в таблице

Сижу, размышляю: можно ли переписать делегата так, чтобы независимо от настроек строк выделялись строки?
Сейчас обсуждают на форуме
u
6 июня 2020 г. 7:26
ubomj

Галерея изображений

delete
s
6 июня 2020 г. 1:54
shuric

Qt/C++ Определение положения курсора над действие(кнопкой) в QToolBar

Доброго дня. Возник вопрос - как можно определить что курсор находится над определенным действием(кнопкой) в qtoolbar ? mainwindow.cpp MainWindow::MainWi…
s
6 июня 2020 г. 0:45
shuric

Qt/C++ особенности QProxyStyle

Да, Вы правы. Код был скопирован с сайта (уже не помню с какого), но решил пойти по пути более легком. Пришлось переписать - кому интересно: использовал stackedWidget для пе…
5 июня 2020 г. 23:08
Алексей

Посоветуйте новичку (базы данных и Qt, что учить)

Блин, а я недавно купил Шлее Qt 5.10 :( С детства хотел стать программистом, баловался Паскалем, писал простенькие программки на Delphi, создавал движок на php, изучал C (забросил и перешел на п…
5 июня 2020 г. 13:09
IscanderChe

QPlainTextEdit настройка цвета фона

Вечер добрый. Пытаюсь настроить цвет фона QPlainTextEdit следующим образом: CodeEditor::CodeEditor(QWidget *parent) : QPlainTextEdit(parent){ ... QPalette::ColorRole role = bac…
О нас
Услуги
© EVILEG 2015-2020
Рекомендует хостинг TIMEWEB