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

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

Content

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

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

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

Алгоритм Дейкстры работает на том основании, что любой подпуть 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;
        }
    }
}

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
s
June 3, 2020, 1:56 a.m.
silo1995

C++ - Тест 003. Условия и циклы

  • Result:35points,
  • Rating points-10
AP
June 2, 2020, 9:11 p.m.
Aleksej Pikenin

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
June 2, 2020, 1:04 p.m.
Daniil Chizhevskij

C++ - Test 001. The first program and data types

  • Result:86points,
  • Rating points6
Last comments
June 4, 2020, 11:10 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Полностью скопировал пример - всё правильно работает. Значит, где-то у меня ошибки в тестовом проекте. Буду разбираться. Извините за беспокойство. :)
June 4, 2020, 7:08 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Во все колонки установили? Нужно на все колонки устанавливать.
June 4, 2020, 6:59 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Код делегата полностью скопировал в свой тестовый проект, но окрашивается не вся строка целиком, а только ячейка, на которую указывает курсор.
June 4, 2020, 6:12 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Добрый день. Удобства ради. В больших проектах удобнее вызывать BaseClass, чем постоянно смотреть, от чего конкретно наследован текущий класс. Экономит время.
Now discuss on the forum
MA
June 4, 2020, 2:46 a.m.
Mihail A

Qt- C++ QTableView подсветить строку

Спасибо.
f
June 3, 2020, 1:49 a.m.
fryn3

Можно ли сделать в QML таблицу как в Excel?

edi-tableview - нашел пока такое выглядит коряво, посмотрим что можно сделать
June 2, 2020, 2:46 a.m.
Evgenij Legotskoj

Медиа файлы Google Firebase

Картинки можете попробовать сжимать через QPixmap, там есть возможность установки scaleFactor, через него можете устанавливать нужные параметры. А что касается конвертации видео, то лучше п…
June 2, 2020, 2:01 a.m.
Evgenij Legotskoj

Перехват обращения к локальным файлам QWebEngineView

В вашем случае вполне адекватное решение. Так сказать меньше зло. В противном случае пришлось бы очень много переписывать и перепиливать.
a
June 1, 2020, 10:26 a.m.
alekseyttrv

SSL на Android

у меня стоит версия Qt 5.14.2. В настройках android поставил openssl из коробки, и этот прроект автоматически стянулся. Достаточно было только добавить в .pro-файл строку после этого и все …
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB