Dijkstra - shortest Path implementation - STL
First: Why use a class?

Graph graph(adjancecy_list, cost_vector);
const auto result = graph.shortest_path(source_node, target_node);


This could easily be refactored to a simple function call of:

const auto result = shortest_path(adjancency_list, cost_vector, source_node, target_node);


Since all shortest_path does is access the classes adjancency_list and cost_vector, which can just be passed in, queue, which should just be a local variable, and is_valid_node, which could just be inlined as you only called it once.

Where you have used the class, there are some minor mistakes. In your constructor, you have initialised adjancecy_list and then cost_list. This should be the other way around (Or you should swap the members). The constructor is also explicit for no reason.

class Graph {
public:
  Graph(const AdjacencyListType &amp;input_list,
        const CostEdgeVector &amp;input_cost_list)
    : adjancecy_list(input_list), cost_list(input_cost_list) {}
  // ...
private:
  // The other way around
  const AdjacencyListType &amp;adjancecy_list;
  const CostEdgeVector &amp;cost_list;
}




      const auto &amp;current_node = queue.top();
      queue.pop();


Is undefined behaviour. You take the const reference of a node, and then you delete it with pop. current_node would then be garbage. Just take a copy:

      const auto current_node = queue.top();
      queue.pop();


You should probably not use reference at all. The objects are all ints or std::tuple&lt;int, int&gt;s, which are very cheap to copy.



This:

    try {
      const auto &amp;target_distance = distance_node.at(target);
      result = target_distance == INFINITY_VALUE ? -1 : target_distance;
    } catch (...) {
      result = -1;
    }


Can be worded in a much clearer way. First, try to avoid catch (...) as much as possible. The only thing that would throw is at, which throws a std::out_of_range, so you can write catch (const std::out_of_range&amp;). However, exceptions are very confusing here. It only throws if target is too big, so you can write something like:

    if (target &gt;= distance_node.size()) {
      result = -1;
    } else {
      const auto target_distance = distance_node[size];
      result = target_distance == INFINITY_VALUE ? -1 : target_distance;
    }


Or even better, change if (!is_valid_node(source)) return -1 to if (!is_valid_node(source) || !is_valid_node(target)) return -1, so that the target will always be in distance_node.

And (this is personal preference) I would avoid the c-like pattern of declaring a result variable. Where you do result = at the end can be replaced with just return, and it's still very clear.



If you are able to control your input, it would probably be easier to, instead of having two vectors which name the neighbour and have the cost of the edge, have a list of neighbours of pairs of nodes and costs. I would declare a helper struct:

struct edge {
  NodeType neighbour;
  CostType cost;
};

// or `using edge = std::pair&lt;NodeType, CostType&gt;;`, but that has less meaning


And have one vector of vector of these.

Also, you use a std::tuple&lt;int, int&gt; for "CostNodeTuple". Since there are only 2 values, it might have been easier to use a std::pair, so std::get&lt;0&gt;(t) turns into t.first, and std::get&lt;1&gt;(t) turns into t.second.

And if you swapped the order, you wouldn't need a custom comparator (As a tuple or pair's operator&lt; does mostly what you want)



If you can do even more refactoring, I would consider using unsigned instead of int, as this doesn't work for negative edge weights (i.e. if there is a negative loop, it should have a value of -infinity). Instead of returning -1 for failure, you could throw an error (if this is an exceptional circumstance) or returning a std::optional&lt;unsigned&gt; (if disjoint graphs are common). The current solution is fine as is though.

Currently, using signed integers, there are a bunch of places where they are implicitly converted to unsigned integers (to use for array indices). It's not too much of a problem, but it shouldn't be the case (Maybe use std::size_t for NodeType?)