Graph implementation with Dijkstra

Question

So, here is the code:

#pragma once
#include <vector>
#include <iostream>
#include <queue>
#include <functional> 

using node = int;
using cost = int;
using arc = std::pair<node, cost>;

using AdjList = std::vector<std::vector<arc>>; // first is node, second is cost


class Graph {
private:
    AdjList adjList;
    std::vector<node> nodes;

public:
    Graph(int n) : nodes{ n },  adjList{ n } {}
    void addEdge(const node v, const node u, const cost c) {
        adjList[v].push_back({ u, c });
        adjList[u].push_back({ v, c });
    }

    std::vector<int> dijkstra(const node n) const {
        std::vector<cost> dist(adjList.size(), INT_MAX);
        std::vector<bool> visited(adjList.size(), false);
        dist[n] = 0;
        std::priority_queue<node, std::vector<node>, std::greater<int>> to_visit;
        to_visit.push(n);
        while (!to_visit.empty()) {
            node v = to_visit.top();
            to_visit.pop();
            visited[v] = true;
            for (const arc& a : adjList[v]) {
                node u = a.first;
                cost c = a.second;
                if (!visited[u] and (dist[u] == INT_MAX or dist[u] > dist[v] + c)) {
                    dist[u] = dist[v] + c;
                    to_visit.push(v);
                }
            }
        }
        return dist;
    }


    friend std::ostream& operator<<(std::ostream& stream, const Graph& g) {
        for (size_t i = 0; i < g.adjList.size(); i++) {
            stream << "node " << i << "\n";
            for (const arc& p : g.adjList[i]) {
                stream << "connected with " << p.first << " cost: " << p.second << " ";
            }
            stream << "\n";
        }
        return stream;
    }


};

I think I did a decent job, but I want to make sure I'm not missing anything. I'm using just a adjacent list for storing the arcs. I was unsure if I should reserve some memory for the vectors there, because maybe it's going to get a little bit slow with the push_back operation, but I also wanted to be able to get rid of the O(n^2) for storing.

Answer 1

Graph seems quite reasonable:
But your distance implementation is not an implementation of Dijkstra.

Dijkstra finds only the cheapest path between two nodes (technically).
But I suppose you can use the technique to find the distance from a node to all others nodes. Dijkstra works by finding the cheapest distance to a node then expanding from there (it never re-expands a node, because it does not need to). To do this you need a sorted frontier list so you always expand from the node with the lowest cost to get there and keep track of nodes that were visited.

---

Some notes:

// Node Id can only by positive.
using node = int;

// Dijkstra assumes all costs are positive.
using cost = int;

Lets have a look at your search:

    // Returning the min distances to all nodes.
    // Sure: but you can not tell what the route to get there is
    //       so this does not help you traverse the graph it only
    //       tells you the shortest distances.
    //       Also how do you tell the difference between a
    //       a distsance of INT_MAX and a node that was never reached.
    std::vector<int> dijkstra(const node n) const {

        // I think this is what is causing you to go wrong.
        // The distance is usually part of the to_visit.
        // You sort the list by the distance.
        std::vector<cost> dist(adjList.size(), INT_MAX);

        // Sure. You need this for dijkstra
        //       In a classic implementation I would have used
        //       std::set<Node> as we don't need (in general) to traverse
        //       the whole graph to find a route from A to B.
        //       Since you are finding the distance to all nodes. This seems
        //       like a better choice.
        std::vector<bool> visited(adjList.size(), false);

        dist[n] = 0;

        // This is a mistake.
        // The order here based on the node-id.
        // It should be based on the cost to get to a node.
        // You always keep it sorted by the cost to get to the node
        // But you may have multiple routes to a node in the list with
        // different costs so after extraction from the list you check
        // if already visited (because if it is already visited then
        // this is not the shortest route).
        //
        // I am sure I could construct a graph that would break this.
        std::priority_queue<node, std::vector<node>, std::greater<int>> to_visit;
        to_visit.push(n);
        while (!to_visit.empty()) {
            node v = to_visit.top();
            to_visit.pop();
            visited[v] = true;
            for (const arc& a : adjList[v]) {
                node u = a.first;
                cost c = a.second;

                // In dijkstra the cost to a node is not known until
                // you actually visit it for the first time (as you may
                // see a node from many other nodes.
                if (!visited[u] and (dist[u] == INT_MAX or dist[u] > dist[v] + c)) {
                    dist[u] = dist[v] + c;
                    to_visit.push(v);
                }
            }
        }
        return dist;
    }

This is what it normally looks like:

    struct DN {
        node  src;
        node  dst;
        cost  c;

        friend bool operator<(DN const& lhs, DN const& rhs) {return lhs.c < rhs.c;}
    };

    std::vector<node> dijkstra(node begin, node end) const
    {
        std::vector<node>       route(adjList.size(), INT_MAX)
        std::set<node>          visited;
        std::priority_queue<DN> frontier;

        frontier.push({INT_MAX, begin, 0});

        while (!frontier.empty()) {
            node v = frontier.top();
            frontier.pop();

            // If we have already been here go to next value.
            if (visited.find(v.dst) != visited.end()]) {
                continue;
            }

            // OK. Found it and save the cost.
            visited.insert(v.dst);
            route[v.dst] = v.src;

            // If we reached the end exit.
            if (v.dst == end) {
                break;
            }

            for (const arc& a : adjList[v.dst]) {
                // Add nodes to frontier list.
                // That is sorted by the cost to the node.
                frontier.push({n, std::get<0>(a), v.c + std::get<1>(a));
            }
        }
        // You can start from the end node
        // and retrace the path the beginning node.
        return route;
    }