Graph implementation with Dijkstra So, here is the code:
#pragma once
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;queue&gt;
#include &lt;functional&gt; 

using node = int;
using cost = int;
using arc = std::pair&lt;node, cost&gt;;

using AdjList = std::vector&lt;std::vector&lt;arc&gt;&gt;; // first is node, second is cost


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


    friend std::ostream&amp; operator&lt;&lt;(std::ostream&amp; stream, const Graph&amp; g) {
        for (size_t i = 0; i &lt; g.adjList.size(); i++) {
            stream &lt;&lt; &quot;node &quot; &lt;&lt; i &lt;&lt; &quot;\n&quot;;
            for (const arc&amp; p : g.adjList[i]) {
                stream &lt;&lt; &quot;connected with &quot; &lt;&lt; p.first &lt;&lt; &quot; cost: &quot; &lt;&lt; p.second &lt;&lt; &quot; &quot;;
            }
            stream &lt;&lt; &quot;\n&quot;;
        }
        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.
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&lt;int&gt; 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&lt;cost&gt; dist(adjList.size(), INT_MAX);

        // Sure. You need this for dijkstra
        //       In a classic implementation I would have used
        //       std::set&lt;Node&gt; 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&lt;bool&gt; 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&lt;node, std::vector&lt;node&gt;, std::greater&lt;int&gt;&gt; to_visit;
        to_visit.push(n);
        while (!to_visit.empty()) {
            node v = to_visit.top();
            to_visit.pop();
            visited[v] = true;
            for (const arc&amp; 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] &gt; 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&lt;(DN const&amp; lhs, DN const&amp; rhs) {return lhs.c &lt; rhs.c;}
    };

    std::vector&lt;node&gt; dijkstra(node begin, node end) const
    {
        std::vector&lt;node&gt;       route(adjList.size(), INT_MAX)
        std::set&lt;node&gt;          visited;
        std::priority_queue&lt;DN&gt; 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&amp; a : adjList[v.dst]) {
                // Add nodes to frontier list.
                // That is sorted by the cost to the node.
                frontier.push({n, std::get&lt;0&gt;(a), v.c + std::get&lt;1&gt;(a));
            }
        }
        // You can start from the end node
        // and retrace the path the beginning node.
        return route;
    }