2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$
  • 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).

\$\endgroup\$
3
\$\begingroup\$

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?)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.