Djkstra algorithm in C++

djkstra.cpp

#include <iostream>
#include <vector>
#include <array>
#include <climits> // INT_MAX
#include <algorithm> // find

using namespace std;

using edges_t = vector<array<int, 2>>;
using graph_t = vector<edges_t>;

struct Node {
  int p = -1;
  int d = INT_MAX;
};

int findMinVertex(const vector<Node>& nodes, const vector<int>& seen) {
  int minVal = INT_MAX, minV;

  for (int i = 0; i < nodes.size(); ++i) {
    if (find(seen.begin(), seen.end(), i) == seen.end() && nodes[i].d < minVal) {
      minVal = nodes[i].d;
      minV = i;
    }
  }

  return minV;
}

vector<int> djkstra(const graph_t& graph, int src, int dst) {
  const int len = graph.size();
  vector<Node> nodes(len);
  
  // Initialization
  for (int i = 0; i < len; ++i) {
    nodes[i] = Node();
  }
  
  nodes[src].d = 0;

  vector<int> seen;

  while (seen.size() < len) {
    const int u = findMinVertex(nodes, seen);
    
    seen.push_back(u);

    edges_t adjacent = graph[u];

    for (const auto& edge : adjacent) {
      int v = edge[0]; // Adjacent vertex
      int w = edge[1]; // Weight
  
      // Relaxation
      if (nodes[v].d > nodes[u].d + w) {
        nodes[v].d = nodes[u].d + w;
        nodes[v].p = u;
      }
    }
  }

  // Construct the path from src to dst
  vector<int> path {dst};

  Node node = nodes[dst];

  while (node.p != -1) {
    path.insert(path.begin(), node.p);
    node = nodes[node.p];
  } 

  return path;
}

int main() {
  graph_t graph(5, edges_t(3));
  
  /*
                     10          1
                 +-------->+1+-------->+2+<--+
                 |         + ^         + ^   |
                 |         | |         | |   |
                 |        2| |        4| |6  |
                 +         | |   7     | |   |
                 0<----------------------+   |
                 +         | |         | |   |
                 |         | |         | |   |9
                 |         | |3        | |   |
                 |         v |         v |   |
                 +-------->+3+-------->+4+   |
                     5       |    2          |
                             +---------------+
  */

  graph[0] = {{1, 10}, {3, 5}};
  graph[1] = {{2, 1}, {3, 2}};
  graph[2] = {{4, 4}};
  graph[3] = {{4, 2}, {2, 9}, {1, 3}};
  graph[4] = {{0, 7}, {2, 6}};

  const vector<int> path = djkstra(graph, 0, 2);

  for (const int& v : path) {
    cout << v << '\n';
  }
}