Dijkstra - shortest Path implementation - STL

Question

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 "Shortest Path" 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 <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <unordered_map>
#include <vector>

namespace {
constexpr int ZERO_DISTANCE_VALUE = 0;
constexpr int INFINITY_VALUE = std::numeric_limits<int>::max();
} // namespace

using NodeType = int;
using CostType = int;
using AdjacencyListType = std::vector<std::vector<NodeType>>;
using DistanceVector = std::vector<NodeType>;
using QueueType = std::queue<NodeType>;
using CostEdgeVector = std::vector<std::vector<CostType>>;
using CostNodeTuple = std::tuple<NodeType, CostType>;
using DistanceMatrixType = std::vector<CostType>;

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

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

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

  std::priority_queue<std::tuple<NodeType, int>,
                      std::vector<std::tuple<NodeType, int>>, QueueComparator>
      queue;

  const CostEdgeVector &cost_list;
  const AdjacencyListType &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 << "Shortest Path value: " << result << std::endl;
  return 0;
}

Answer 1

• spelling: adjancecy_list

• The Graph class doesn't own the cost list or the adjacency list, or do anything graph-like. It should probably be called PathFinder or simply turned into a free function, e.g.:

  ShortestPathSearchResult FindShortestPath(const AdjacencyListType&, const CostEdgeVector&, const NodeType& source, const NodeType& destination);
  

• NodeType is really an index so it should probably be NodeIndex instead, and be the same type as used for indexing the adjacency list and cost list (std::size_t).

• int is used in several places where we should be using NodeType or CostType instead.

• Bug: In the simple example given, both the adjacency and cost list are empty (i.e. there are no nodes). However, shortest_path returns 0 for the given target / source node index, instead of -1. This is because it checks for equality between the source and target nodes before checking that the nodes actually exist.

• It's better to throw an exception when given invalid input (nodes that don't exist). Currently there's no difference between invalid input (returns -1) and simply not being able to find a path.

• Don't use exceptions for flow control (the try catch block). We can simply check the target index is valid earlier in the function (as with the source index).

Answer 2

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 &input_list,
        const CostEdgeVector &input_cost_list)
    : adjancecy_list(input_list), cost_list(input_cost_list) {}
  // ...
private:
  // The other way around
  const AdjacencyListType &adjancecy_list;
  const CostEdgeVector &cost_list;
}

---

      const auto &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<int, int>s, which are very cheap to copy.

---

This:

    try {
      const auto &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&). However, exceptions are very confusing here. It only throws if target is too big, so you can write something like:

    if (target >= 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<NodeType, CostType>;`, but that has less meaning

And have one vector of vector of these.

Also, you use a std::tuple<int, int> for "CostNodeTuple". Since there are only 2 values, it might have been easier to use a std::pair, so std::get<0>(t) turns into t.first, and std::get<1>(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< 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<unsigned> (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?)