Найти кратчайший путь от вершины 0 к вершине б с помощью алгоритма Дейкстры

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

По дате

По рейтингу

tatiana_41026

Просветленный

1г

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

Алгоритм Дейкстры
Инициализация: Устанавливаем расстояние до начальной вершины 0 равным 0, а до всех остальных вершин - бесконечность. Создаем множество необработанных вершин.

Обработка: Повторяем следующие шаги, пока есть необработанные вершины:

Выбираем вершину с наименьшим расстоянием.
Обновляем расстояния до соседних вершин.
Помечаем текущую вершину как обработанную.
Завершение: Когда вершина назначения будет обработана, алгоритм завершается.

Шаги программы
Создаем структуру данных для представления графа.
Реализуем алгоритм Дейкстры для поиска кратчайшего пути.
Выводим результат.
код на C++

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182

 #include <iostream> 
#include <vector> 
#include <limits> 
#include <queue> 
 
using namespace std; 
 
// Определение структуры для представления графа 
struct Edge { 
    int destination; 
    int weight; 
}; 
 
void dijkstra(const vector<vector<Edge>>& graph, int source, int destination) { 
    int n = graph.size(); 
    vector<int> distances(n, numeric_limits<int>::max()); 
    vector<int> previous(n, -1); 
    distances[source] = 0; 
 
    // Приоритетная очередь для хранения вершин по наименьшему расстоянию 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 
    pq.push({0, source}); 
 
    while (!pq.empty()) { 
        int current = pq.top().second; 
        int current_distance = pq.top().first; 
        pq.pop(); 
 
        if (current_distance > distances[current]) { 
            continue; 
        } 
 
        for (const Edge& edge : graph[current]) { 
            int next = edge.destination; 
            int weight = edge.weight; 
            int distance = current_distance + weight; 
 
            if (distance < distances[next]) { 
                distances[next] = distance; 
                previous[next] = current; 
                pq.push({distance, next}); 
            } 
        } 
    } 
 
    // Печать кратчайшего пути 
    if (distances[destination] == numeric_limits<int>::max()) { 
        cout << "Нет пути от вершины " << source << " до вершины " << destination << endl; 
    } else { 
        cout << "Кратчайший путь от вершины " << source << " до вершины " << destination << " равен " << distances[destination] << endl; 
        cout << "Путь: "; 
        vector<int> path; 
        for (int at = destination; at != -1; at = previous[at]) { 
            path.push_back(at); 
        } 
        for (auto it = path.rbegin(); it != path.rend(); ++it) { 
            cout << *it << " "; 
        } 
        cout << endl; 
    } 
} 
 
int main() { 
    // Определение графа 
    vector<vector<Edge>> graph(8); 
    graph[0] = {{1, 2}, {2, 5}}; 
    graph[1] = {{2, 2}, {3, 3}, {4, 8}}; 
    graph[2] = {{5, 4}}; 
    graph[3] = {{1, 3}, {4, 2}, {6, 5}}; 
    graph[4] = {{5, 3}, {7, 15}}; 
    graph[5] = {{7, 10}}; 
    graph[6] = {{7, 13}}; 
    graph[7] = {}; // вершина 7 не имеет исходящих ребер 
 
    int source = 0; 
    int destination = 6; 
 
    dijkstra(graph, source, destination); 
 
    return 0; 
}