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