Dijkstra - shortest Path implementation - STL I have implemented Dijkstra algorithm to perform Shortest Path problem.
Input:
Adjacency List(Directed Graph): Description is like that
{Source Node, {edge_1, .. , edge_N}}
Cost Matrix (Same format as Adjacency List)
Queue: Priority Queue
Input to &quot;Shortest Path&quot; method are Start Node, End Node; it returns -1 if
there is no path from Source Node to Target Node, else it returns the cost of the minimum path selected.
Code:
#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;limits&gt;
#include &lt;queue&gt;
#include &lt;tuple&gt;
#include &lt;unordered_map&gt;
#include &lt;vector&gt;

namespace {
constexpr int ZERO_DISTANCE_VALUE = 0;
constexpr int INFINITY_VALUE = std::numeric_limits&lt;int&gt;::max();
} // namespace

using NodeType = int;
using CostType = int;
using AdjacencyListType = std::vector&lt;std::vector&lt;NodeType&gt;&gt;;
using DistanceVector = std::vector&lt;NodeType&gt;;
using QueueType = std::queue&lt;NodeType&gt;;
using CostEdgeVector = std::vector&lt;std::vector&lt;CostType&gt;&gt;;
using CostNodeTuple = std::tuple&lt;NodeType, CostType&gt;;
using DistanceMatrixType = std::vector&lt;CostType&gt;;

class Graph {
public:
  explicit Graph(const AdjacencyListType &amp;input_list,
                 const CostEdgeVector &amp;input_cost_list)
      : adjancecy_list(input_list), cost_list(input_cost_list) {}

  struct QueueComparator {
    bool operator()(const CostNodeTuple &amp;left, const CostNodeTuple &amp;right) {
      return std::get&lt;1&gt;(left) &lt; std::get&lt;1&gt;(right);
    }
  };

  int shortest_path(const int &amp;source, const int &amp;target) {
    int result = 0;
    if (source == target)
      return result;
    if (!is_valid_node(source))
      return -1;
    std::vector&lt;int&gt; distance_node(adjancecy_list.size(), INFINITY_VALUE);
    distance_node[source] = 0;
    queue.emplace(std::make_tuple(source, 0));
    while (!queue.empty()) {
      const auto &amp;current_node = queue.top();
      queue.pop();
      const NodeType &amp;current_node_index = std::get&lt;0&gt;(current_node);
      const auto &amp;sub_node_vector = adjancecy_list.at(current_node_index);
      const auto &amp;sub_node_cost = cost_list.at(current_node_index);
      const int &amp;current_distance_cost = distance_node.at(current_node_index);
      for (NodeType index = 0; index &lt; sub_node_vector.size(); ++index) {
        const auto &amp;child_index = sub_node_vector.at(index);
        const int relaxation_value =
            current_distance_cost + sub_node_cost.at(index);

        if ((distance_node.at(child_index) &gt; relaxation_value)) {
          distance_node[child_index] = relaxation_value;
          queue.emplace(std::make_tuple(child_index, relaxation_value));
        }
      }
    }
    try {
      const auto &amp;target_distance = distance_node.at(target);
      result = target_distance == INFINITY_VALUE ? -1 : target_distance;
    } catch (...) {
      result = -1;
    }

    return result;
  }

private:
  bool is_valid_node(const NodeType &amp;node) {
    return node &lt; adjancecy_list.size();
  }

  std::priority_queue&lt;std::tuple&lt;NodeType, int&gt;,
                      std::vector&lt;std::tuple&lt;NodeType, int&gt;&gt;, QueueComparator&gt;
      queue;

  const CostEdgeVector &amp;cost_list;
  const AdjacencyListType &amp;adjancecy_list;
};

int main() {
  AdjacencyListType cost_vector;
  CostEdgeVector adjancecy_list;
  NodeType source_node = 0;
  NodeType target_node = 0;
  Graph graph(adjancecy_list, cost_vector);
  const auto result = graph.shortest_path(source_node, target_node);
  std::cout &lt;&lt; &quot;Shortest Path value: &quot; &lt;&lt; result &lt;&lt; std::endl;
  return 0;
}
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?)