mafulechka
mafulechkaТам. 15, 2019, 4:22 Т.Ж.

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

Дейкстра алгоритмі графиктегі кез келген екі төбенің арасындағы ең қысқа жолды табуға мүмкіндік береді.

Оның ең аз таралатын ағаштан айырмашылығы, екі төбенің арасындағы ең қысқа қашықтық графиктегі барлық төбелерді қамтымауы мүмкін.


Дейкстра алгоритмі қалай жұмыс істейді

Дейкстра алгоритмі A және D төбелері арасындағы ең қысқа жолдың A -> D жолының кез келген B -> 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++ тілінде Dijkstra алгоритмінің орындалуы төменде келтірілген. Кодтың күрделілігін жақсартуға болады, бірақ абстракциялар кодты алгоритммен байланыстыру үшін жақсы.

#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 хостинг.

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

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

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

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

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

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

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз