Dijkstra's Algorithm implementation in C++

Question

After applying suggestions from here about Bellman Ford Algorithm. Help me to improve this program.

#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);
}

Answer 1

Design:

I personally don't like that you have combined the data structure and algorithm into a single thing. BUT if your use case is very specific this can be OK.

Personally I would separate the Graph and the Algorithm into seprate entities. Then provide a very simple interface that allows the algorithm accesses to the data without needing to know the exact type.

Graph Design

Not sure why you need to store the edge information in two different places.

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

I would simply store the weight as part of the adjacency list.

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

Also prefer std::vector<> over std::list<>. There are a few very specific use cases where list is better but on average it is best to default to a vector then measure and optimize later.

Code Review

Emplace Back

You can simplify this:

    vertices.push_back(Vertex(i));

To

    vertices.emplace_back(i);

The difference is that push_back() uses a temporary object that is copied into the container. While emplace_back() constructs the contained type in place by passing its parameters to the contained types constructor.

Always use braces

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

There is nothing technically wrong. But this is a sloppy habit that will one day cause you untold grief that will be very hard to de-bug. Always use {} around sub-blocks.

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

This because the sub-block is a single statement or a block of statements surrounded by {}. The trouble is that some function calls are not actually function calls but macros disguised as function calls. These macros can potentially be multi line statements (only the first of which is bound to the if statement.

Exception safety.

You must make the best effort to make your code exception safe. This means either the operation works or if it fails (and throws) then the object remains unchanged.

The problem is here:

    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");