Реализация алгоритма Дейкстры на C++


После применения предложения здесь о Беллман Форд алгоритм. Помочь мне улучшить эту программу.

#include <iostream>
#include <vector>
#include <map>
#include <limits>
#include <list>
#include <queue>

class Graph
{
    enum Color {WHITE, BLACK};

    struct Vertex
    {
        std::size_t id;
        int distance = std::numeric_limits<int>::max();
        Color color = WHITE;
        Vertex(std::size_t id) : id(id) {}
    };

    struct Edge
    {
        std::size_t from;
        std::size_t to;
        bool operator<(const Edge& other) const
        {
            return std::tie(from, to) < std::tie(other.from, other.to);
        }
    };

    std::vector<Vertex> vertices = {};
    std::map<Edge, int> edge_weight = {};
    std::vector< std::list<std::size_t> > adj_list = {};
    //to store processed vertex
    std::vector<std::size_t> processed  = {};

    //distance from aource, vertex id
    typedef std::pair<int, std::size_t> dist_from_source;
    //to store unprocessed vertex min-priority queue
    std::priority_queue<dist_from_source, std::vector<dist_from_source>,
                        std::greater<dist_from_source>> unprocessed;

  public:
    Graph(std::size_t size);
    void add_edge(std::size_t src, std::size_t dest, int weight);
    void dijkstra(std::size_t src);
    std::ostream& print_distance(std::ostream&) const;
    std::ostream& print_path(std::ostream&) const;

  private:
    void relax(std::size_t src, std::size_t dest, int weight);
};

Graph::Graph(std::size_t size)
{
    vertices.reserve(size);
    adj_list.resize(size);
    for (int i = 0; i < size; i++)
    {
        vertices.push_back(Vertex(i));
    }
}

void Graph::add_edge(std::size_t src , std::size_t dest, int weight)
{
    if(weight >= 0)
    {
        if (src == dest)
            throw std::logic_error("src == dest");

        if (src < 0 || vertices.size() <= src)
            throw std::out_of_range("src");

        if (dest < 0 || vertices.size() <= dest)
            throw std::out_of_range("dest");

        //insert into adjacency list
        adj_list[src].push_back(dest);

        //insert vertices with their associated weight
        const auto inserted = edge_weight.insert( { Edge{src, dest}, weight });
        if (!inserted.second)
            throw std::logic_error("existing edge");
    }
    else
        std::cerr << "Negative weight\n";
}

void Graph::relax(std::size_t src, std::size_t dest, int weight)
{
    auto& next_dist = vertices[dest].distance;
    const auto curr_dist = vertices[src].distance + weight;
    if (curr_dist < next_dist)
    {
        next_dist = curr_dist;
        //update distance in unprocessed queue
        unprocessed.push( std::make_pair(next_dist, dest));
    }
}

void Graph::dijkstra(std::size_t src)
{
    //initialize distance of source
    vertices[src].distance = 0;

    unprocessed.push( std::make_pair(vertices[src].distance, src) );
    while (!unprocessed.empty())
    {
         int curr_vertex_dist = unprocessed.top().first;
         std::size_t curr_vertex = unprocessed.top().second;
         unprocessed.pop();

        if (vertices[curr_vertex].color == WHITE)
        {
            processed.push_back(curr_vertex);
        }
        vertices[curr_vertex].color = BLACK;
        for (auto& ver: adj_list[curr_vertex])
        {
            for(auto edge: edge_weight)
            {
                 relax(edge.first.from, edge.first.to, edge.second);
            }
        }
    }
}

std::ostream& Graph::print_distance(std::ostream& os) const
{
    os << "Vertex\t\tDistance from Source\n";
    for (auto vertex: vertices)
    {
        os << vertex.id << "\t\t" << vertex.distance << "\n";
    }
    return os;
}

std::ostream& Graph::print_path(std::ostream& os) const
{
    std::cout << "Path : ";
    for (int i = 0; i < processed.size() - 1; i++)
    {
        os << processed[i] << "-->";
    }
    os << processed.back() << "\n";
}


int main()
{
    Graph grp(5);
    grp.add_edge(0, 1, 10);
    grp.add_edge(0, 2, 5);
    grp.add_edge(1, 3, 1);
    grp.add_edge(1, 2, 2);
    grp.add_edge(2, 1, 3);
    grp.add_edge(2, 3, 9);
    grp.add_edge(2, 4, 2);
    grp.add_edge(3, 4, 4);
    grp.add_edge(4, 3, 6);
    grp.add_edge(4, 0, 7);
    grp.dijkstra(0);
    grp.print_distance(std::cout);
    grp.print_path(std::cout);
}


517
0
задан 8 марта 2018 в 05:03 Источник Поделиться
Комментарии
1 ответ

Дизайн:

Мне лично не нравится, что у вас смешанная структура данных и алгоритм в единую вещь. Но если в вашем случае весьма специфична, это может быть ОК.

Лично я хотел бы отделить Graph и Algorithm в самостоятельные сущности. Тогда предлагаем очень простой интерфейс, который позволяет алгоритм доступа к данным без необходимости знать точный тип.

Дизайн Графика

Не уверен, почему вы должны хранить данные в двух разных местах.

std::map<Edge, int> edge_weight = {};
std::vector< std::list<std::size_t> > adj_list = {};

Я бы просто хранить вес в составе списка смежности.

std::vector<std::vector<std::pair<Dst, Weight>>>  adjacencyList;

Тоже предпочитаю std::vector<> за std::list<>. Есть несколько очень конкретных случаях, когда список лучше, но в среднем лучше чем стандартный вектор, измерить и оптимизировать позже.

Комментарий Код

Размещай Назад

Вы можете упростить это:

    vertices.push_back(Vertex(i));

Для

    vertices.emplace_back(i);

Разница в том, что push_back() использует временный объект, который копируется в контейнер. А emplace_back() создает типа в помещение путем передачи его параметры, содержащиеся видах конструктор.

Всегда используйте фигурные скобки

    if (src == dest)
throw std::logic_error("src == dest");

Нет ничего технически неправильно. Но это неряшливые привычки, которая в один день вызывают у вас невыразимое горе, что будет очень трудно де-ошибка. Всегда используйте {} вокруг подблоков.

    if (src == dest) {
throw std::logic_error("src == dest");
}

Это потому, что суб-блоке один оператор или блок операторов, в окружении {}. Беда в том, что некоторые функции на самом деле не вызов функции, а макросы замаскированный вызов функции. Эти макросы могут быть многоканальный заявления (только первый из которых связан с if statement.

Исключение безопасности.

Вы должны приложить все усилия, чтобы сделать ваш код исключения безопасным. Это означает либо операции или, если это не удается (и бросает), то объект остается неизменным.

Проблема здесь:

    adj_list[src].push_back(dest);

// At this point your object is modified.
// If you throw an exception at this point then you have
// not provided the strong exception guarantee.

const auto inserted = edge_weight.insert( { Edge{src, dest}, weight });
if (!inserted.second) {
// If you throw here your object is in an invalid state.
// It has an edge in the adjacency list that has
// an invalid weight.
throw std::logic_error("existing edge");

4
ответ дан 8 марта 2018 в 07:03 Источник Поделиться