Ошибка алгоритма кратчайшего пути Дейкстры - PullRequest
Новая
       39

Ошибка алгоритма кратчайшего пути Дейкстры

0 голосов
/ 19 мая 2018

Я написал следующий код для реализации алгоритма кратчайшего пути Дейкстры: 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <functional>
#include <list>
#include <cstring>

int findPath(std::vector<std::list<std::pair<int, int>>> graph, int x, int y) {
    int n = graph.size();
    std::priority_queue < std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push(std::pair<int, int>(0, x));
    int *visited = new int[n + 1]{};
    int *distance = new int[n + 1];
    memset(distance, -1, sizeof(*distance) * (n + 1));
    distance[x] = 0;

    int current;
    while (!pq.empty()) {
        current = pq.top().second;
        pq.pop();
        if (current == y) {
            return distance[y];
        }
        if (!visited[current]) {
            visited[current] = 1;
            for (std::list<std::pair<int, int>>::iterator it = graph[current].begin(); it != graph[current].end(); it++) {
                if (!visited[it->first]) {
                    if (distance[it->first] == -1 || distance[it->first] > distance[current] + it->second) {
                        distance[it->first] = distance[current] + it->second;
                        pq.push(std::pair<int, int>(distance[it->first], it->first));
                    }
                }
            }
        }
    }
    return distance[y];
}

int main()
{
    std::ios::sync_with_stdio(false);

    int n;
    int m;
    int x;
    int y;

    std::cin >> n >> m >> x >> y;

    int a;
    int b;
    int c;

    std::vector<std::list<std::pair<int, int>>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        std::cin >> a >> b >> c;
        graph[a].push_back(std::pair<int, int>(b, c));
    }

    std::cout << findPath(graph, x, y) << std::endl;

    return 0;
}

Ввод N - количество вершин, M - количество ребер, x, y - 2 вершины.Тогда у вас есть M линий a, b, c, что означает, что у вас есть путь от a до b с расстоянием c.

Также вы можете иметь несколько ребер из одной вершины в другую.

Цель состоит в том, чтобы найти кратчайший путь от х до у.(-1, если пути нет) Я использую приоритетную очередь пар (первая - текущее расстояние до вершины, а вторая - вершина).

Код работает для некоторых тестов и даетнеправильный ответ для остальных (от системы судьи, поэтому я не вижу, что это за тесты).

Я смотрел на это в течение часа и не могу понять, почему это не так.работает.

Буду признателен, если вы обнаружите ошибку и почему она не работает.

Пример ввода:

5 5 1 5

1 2 1

1 3 2

2 4 4

3 4 4

4 5 5

Выход: 10

РЕДАКТИРОВАТЬ: Кажется, в коде нет ошибок.Задача была неоднозначной в том смысле, что если есть путь от a до b, то есть путь от b до a.Это была ошибка.

...