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

Дерево, Алгоритм, 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

Комментарии

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

Здравствуйте, уважаемые пользователи EVILEG !!!

Если сайт вам помог, то поддержите разработку сайта финансово, пожалуйста.

Вы можете сделать это следующими способами:

Спасибо, Евгений Легоцкой

О
18 ноября 2019 г. 15:54
Оксана

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

  • Результат:66баллов,
  • Очки рейтинга-1
АГ
18 ноября 2019 г. 15:50
Антон Гурьев

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

  • Результат:46баллов,
  • Очки рейтинга-6
VZ
17 ноября 2019 г. 2:25
Vladimir Zhitkovsky

Qt - Тест 001. Сигналы и слоты

  • Результат:78баллов,
  • Очки рейтинга2
Последние комментарии
c
18 ноября 2019 г. 6:27
cyberaxe77

Моих знаний пока явно недостаточно, чтобы писать статьи. Так...небольшие заметки "на полях"))).
18 ноября 2019 г. 6:10
Евгений Легоцкой

Пока что на сайте нет активных пользователей PyQt5, кто бы мог писать статьи по PyQt5, к сожалению. Лично я только для статей пользуюсь этой библиотекой. Но можете стать одним из первых ;) Любой…
18 ноября 2019 г. 2:44
Евгений Легоцкой

Добрый день. На тот момент ничего не использовал дополнительно и никаких специальных настроек не делал. Просто собрал и получилось 10 мб.
c
17 ноября 2019 г. 14:25
cyberaxe77

Шикарно! Как обычно всё объясняется чётко, ясно и, по-возможности, кратко. Побольше бы контента по PyQt5...
ГВ
16 ноября 2019 г. 16:16
Гибралтар Вольфрамов

Разрешите узнать, как вы получили qt+qml приложение размером в 10мб(даже релизных). Дело в том, что пустое приложение, хоть и со стек вью, обходится мне на все 40мб пространства. Или же вы воспо…
Сейчас обсуждают на форуме
19 ноября 2019 г. 5:13
Евгений Легоцкой

Привет. Недостаточно иноформации. Нужно описание метода в C++, а также код, вызывающий метод в QML
19 ноября 2019 г. 5:04
Евгений Легоцкой

label - это GUI элемент в данном случае? Если так, то я бы не стал раскидывать GUI элементы в разные потоки. Дело в том, что в документации на Qt, сказано, что GUI элементы работают только в GUI…
MP
19 ноября 2019 г. 4:13
Mikhail Petrov

Без разницы в дизайнере создается форма или не в дизайнере. Как вы добавляете в QTabWidget?
19 ноября 2019 г. 2:36
BlinCT

Всем привет. Если кто дебажил qml часть подскажиет пожалуйста, какие настрйоки требуются в Qt Creator? Я собирал 5.12.5 из исходников, в Настройкс в debugger у меня выставлен путь к со…
18 ноября 2019 г. 13:36
Intruder

Понятно. Я кстати так сейчас и сделал, добавил проект в проект и т.д. Спасибо!
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB