# c++ – Graph implementation with Dijkstra

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:
std::vector<node> nodes;

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

std::vector<int> dijkstra(const node n) const {
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.

Posted on Categories Articles