Dijkstra's Algorithm for Shortest Paths in C++

Дейкстра за O(M log N), C++

ограничение по времени на тест 2 секунды ограничение по памяти на тест 64 мегабайта Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины S до всех остальных. Программа должна работать быстро для больших разреженных графов. Также выведите вершины, входящие в кратчайший путь между вершинами S и F.

Входные данные Первая строка содержит три числа N, M, S, F – количество вершин, количество ребер, стартовая вершина и конечная вершина графа соответственно (1 ≤ N ≤ 60000, 1 ≤ M ≤ 200000, 0 ≤ S, F ≤ N - 1). Вершины в графе нумеруются с 0 до N-1. Далее следуют M строк, каждая из которых содержит по три целых числа. Первые два из них в пределах от 0 до N-1 обозначают концы соответствующего ребра, третье – в пределах от 0 до 20 000 обозначает длину этого ребра.

Выходные данные В первой строке выведите N целых чисел – кратчайшие расстояния от вершины с номером S до 0-й, 1-й, 2-й и т.д вершин. Если некоторая вершина недостижима, вместо расстояния выведите число -1. Затем, во второй строке выведите количество вершин, входящие в кратчайший путь между вершинами S и F. В третьей строке выведите сами вершины, входящие в кратчайший путь (если кратчайших путей несколько, можно вывести любой их них). Если вершина F недостижима, во второй строке выведите -1.

Пример входные данные 5 7 1 3 1 2 5 1 3 2 2 3 4 2 4 3 3 4 6 0 3 20 0 4 10 выходные данные 18 0 5 2 8 2 1 3

Для решения задачи о нахождении кратчайших расстояний в неориентированном взвешенном графе с использованием алгоритма Дейкстры, мы можем воспользоваться приоритетной очередью (например, с помощью std::priority_queue в C++). Мы также будем хранить предшественников для восстановления пути от стартовой вершины до конечной.

Вот пример реализации на C++:

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <utility>

using namespace std;

const int INF = numeric_limits<int>::max();

struct Edge {
    int to, weight;
};

void dijkstra(int N, int S, const vector<vector<Edge>>& graph, vector<int>& distances, vector<int>& predecessors) {
    distances.assign(N, INF);
    predecessors.assign(N, -1);
    distances[S] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, S});

    while (!pq.empty()) {
        int current_distance = pq.top().first;
        int current_vertex = pq.top().second;
        pq.pop();

        if (current_distance > distances[current_vertex]) {
            continue;
        }

        for (const Edge& edge : graph[current_vertex]) {
            int new_distance = current_distance + edge.weight;
            if (new_distance < distances[edge.to]) {
                distances[edge.to] = new_distance;
                predecessors[edge.to] = current_vertex;
                pq.push({new_distance, edge.to});
            }
        }
    }
}

vector<int> reconstruct_path(int S, int F, const vector<int>& predecessors) {
    vector<int> path;
    for (int v = F; v != -1; v = predecessors[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    int N, M, S, F;
    cin >> N >> M >> S >> F;

    vector<vector<Edge>> graph(N);
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w}); // так как граф неориентированный
    }

    vector<int> distances, predecessors;
    dijkstra(N, S, graph, distances, predecessors);

    // Вывод расстояний
    for (int i = 0; i < N; ++i) {
        if (distances[i] == INF) {
            cout << -1 << " ";
        } else {
            cout << distances[i] << " ";
        }
    }
    cout << endl;

    // Восстановление пути от S до F
    if (distances[F] == INF) {
        cout << -1 << endl;
    } else {
        vector<int> path = reconstruct_path(S, F, predecessors);
        cout << path.size() << endl;
        for (int v : path) {
            cout << v << " ";
        }
        cout << endl;
    }

    return 0;
}

Объяснение кода:

1. Структура Edge: Определяет ребро графа с указанием конечной вершины и веса.
2. Функция dijkstra: Реализует алгоритм Дейкстры. Она принимает количество вершин, стартовую вершину, граф и возвращает расстояния и предшественников.
3. Функция reconstruct_path: Восстанавливает путь от стартовой до конечной вершины, используя массив предшественников.
4. Основная функция main: Читает входные данные, строит граф, вызывает алгоритм Дейкстры и выводит результаты.

Входные данные:

Программа ожидает, что входные данные будут предоставлены в формате, описанном в задаче.

Выходные данные:

Программа выводит кратчайшие расстояния от стартовой вершины до всех остальных, количество вершин на кратчайшем пути от S до F и сам путь. Если путь недостижим, выводится -1.