###Input:

#Code:

Input:

Code:

I have implemented Dijkstra algorithm to perform Shortest Path problem. Input:

Cost Matrix (Same format as Adjacency List) Queue: Priority Queue Input to "Shortest Path" method are Start Node, End Node and it return -1 if there is no Path from Source Node to Target Node, else it return 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;
}

I have implemented Dijkstra algorithm to perform Shortest Path problem.

###Input:

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;
}