Dijkastras Shortest Path Algorithm between two vertices on a graph Write a program (dij.cpp) that does the following: - Leverages the provided includes to accomplish the following: o min-heap.h: determine the most desirable vertex to process next o graph.h: read in a graph from a text file and store its adjacency matrix for read-only access o set.h: keep track of vertices that have already been visited o stack.h: output the vertices in the shortest path o list.h: used to implement Set and Stack - You should accept a file name of the graph you want to test (assume the file is in the same directory as the cpp program) - Load the graph into memory with the Graph class - Accept two index values representing the source vertex and target vertex - Run Dijkstras Shortest Path Algorithm on the loaded graph using the source and target vertex - Output the entirety of the determined shortest path, with the distance of each edge in the path and the total path between the two vertices

min_heap.h

#ifndef MIN_HEAP_H #define MIN_HEAP_H #include  #include  // Heap implementation derived from: // https://www.geeksforgeeks.org/binary-heap/ class MinHeap { private: // Creating internal "nested" classes is an alternative // to friending entire classes. This way, only MinHeap has access // to the a HeapNode object and its contents. class HeapNode { public: int priority; int value; HeapNode() { value = priority = 0; } HeapNode(int v, int p) { value = v; priority = p; } ~HeapNode() { value = priority = 0; } }; std::vector* heap; void swap_heap_node(int, int); void min_heapify(int); public: MinHeap() { heap = new std::vector(); heap->push_back(new HeapNode(0,0)); } ~MinHeap(); bool is_empty() { return size() int parent(int index) { return index / 2; } int left(int index) { return 2 * index; } int right(int index) { return 2 * index + 1; } int min() { return (*heap)[0]->value; } int extract_min(); int size() { return heap->size() - 1; } void insert(int, int); bool decrease_priority(int, int); void print(); }; MinHeap::~MinHeap() { while (heap->size()) { delete (*heap)[size()]; heap->pop_back(); } delete heap; } void MinHeap::swap_heap_node(int x, int y) { int p = (*heap)[x]->priority; int v = (*heap)[x]->value; (*heap)[x]->priority = (*heap)[y]->priority; (*heap)[x]->value = (*heap)[y]->value; (*heap)[y]->priority = p; (*heap)[y]->value = v; } void MinHeap::min_heapify(int index) { int lc = left(index); int rc = right(index); int smallest = index; // do comparisons with child nodes to determine small value // if l or r is > size, then there is no node at that index if (lc priority priority) smallest = lc; if (rc priority priority) smallest = rc; if (smallest != index) // if the node at index is not the smallest, perculate down the heap { swap_heap_node(index, smallest); min_heapify(smallest); // check again if we need to perculate down another level } } int MinHeap::extract_min() { int min_value; if (is_empty()) exit(1); if (size() == 1) { min_value = (*heap)[size()]->value; delete (*heap)[size()]; heap->pop_back(); return min_value; } min_value = (*heap)[1]->value; // copy min value before delete the top node swap_heap_node(1, size()); // swap min node with last node delete (*heap)[size()]; // delete last node (prev min node) heap->pop_back(); min_heapify(1); // reheapify starting at root node (index 1) return min_value; } void MinHeap::insert(int value, int priority) { heap->push_back(new HeapNode(value, priority)); int index = size(); // position new node correctly in min heap while ( index != 1 && (*heap)[parent(index)]->priority > (*heap)[index]->priority) { // since the new node is smaller than its parent, // we the nodes to swap places. swap_heap_node(index, parent(index)); index = parent(index); // update the index to reflect our new position in the heap } } bool MinHeap::decrease_priority(int value, int priority) { for (int i = 1; i if ((*heap)[i]->value == value) { (*heap)[i]->priority = priority; while (i != 1 && (*heap)[parent(i)]->priority > (*heap)[i]->priority) { swap_heap_node(i, parent(i)); i = parent(i); } return true; } } return false; } void MinHeap::print() { for (int i = 1; i priority  
graph.h
 
#ifndef GRAPH_H #define GRAPH_H #include  #include  #include  #include  class Graph { private: int adj_matrix_size; int* adj_matrix; bool filled; public: Graph() { adj_matrix_size = 0; adj_matrix = 0; filled = false; }; ~Graph(); bool create_graph(std::string); int get_weight(int, int); void print_adj_matrix(); int dimension() { return adj_matrix_size; } }; Graph::~Graph() { filled = false; for (int r = 0; r for (int c = 0; c if (adj_matrix) delete adj_matrix; } bool Graph::create_graph(std::string path) { // open file with input file stream on given path std::ifstream fs(path); std::string line; // check for errors openign file if (!fs.is_open()) return false; // clear any existing graph data adj_matrix_size = 0; filled = false; if (adj_matrix) { delete adj_matrix; adj_matrix = 0; } // get matrix size from first line std::getline(fs, line); std::istringstream ss(line); ss >> adj_matrix_size; // create square matrix to store graph information adj_matrix = new int[adj_matrix_size * adj_matrix_size]; for (int r = 0; r if (!std::getline(fs, line)) return false; // clear previous flag, set iss to read over new string ss.clear(); ss.str(line); for (int c = 0; c if (!(ss >> adj_matrix[r * adj_matrix_size + c])) return false; // exit if reading token failed } } if (fs.bad()) return false; fs.close(); filled = true; return true; } int Graph::get_weight(int row, int column) { if (row return adj_matrix[row * adj_matrix_size + column]; } void Graph::print_adj_matrix() { for (int r = 0; r for (int c = 0; c  
set.h 
 
#ifndef SET_H #define SET_H #include "list.h" class Set { private: List* list; int set_size; public: Set() { list = new List(); set_size = 0; } ~Set() { delete list; } bool contains(int value) { return list->contains(value); } bool add(int); bool remove(int); void clear(); void print(); int size() { return set_size; } }; bool Set::add(int value) { if (list->contains(value)) return false; list->addToTail(value); ++set_size; return true; } bool Set::remove(int value) { if (list->contains(value)) return list->remove(value); return false; } void Set::print() { const ListNode* temp = list->getHead(); while (temp != 0) { std::cout valueOf(temp) getNext(temp); } std::cout  
stack.h 
 
 
 
#ifndef STACK_H #define STACK_H #include "list.h" class Stack { private: List* list; public: Stack() { list = new List(); } ~Stack() { delete list; } bool isEmpty() { return list->isEmpty(); } void clear() { list->clear(); } void push(int data) { list->addToHead(data); } int pop() { return list->removeHead(); } int top() { return list->valueOf(list->getHead()); } }; #endif 
 
list.h 
 
#ifndef LIST_H #define LIST_H class ListNode { private: int data; ListNode* prev; ListNode* next; public: ListNode() { data = 0; prev = next = 0; } ListNode(int d, ListNode* p, ListNode* n) { data = d; prev = p; next = n; } ~ListNode() { data = 0; prev = next = 0; } friend class List; }; class List { private: ListNode* head; ListNode* tail; int removeNode(ListNode*); public: List() { head = tail = 0; } ~List(); void clear(); bool isEmpty() { return head == 0; } bool contains(int value); void addToHead(int value); void addToTail(int value); int removeHead(); int removeTail(); int removeAt(int index); bool remove(int value); int at(int index); int valueOf(const ListNode* elem); const ListNode* getNext(const ListNode* node); const ListNode* getPrevious(const ListNode* node); const ListNode* getHead() { return head; } const ListNode* getTail() { return tail; } }; List::~List() { clear(); } void List::clear() { while (!isEmpty()) removeTail(); } int List::removeNode(ListNode* node) { if (node == head) return removeHead(); if (node == tail) return removeTail(); int value = node->data; node->prev->next = node->next; node->next->prev = node->prev; delete node; return value; } bool List::contains(int value) { ListNode *temp = head; while (temp != 0 && temp->data != value) temp = temp->next; return temp != 0; } void List::addToHead(int value) { if (isEmpty()) { head = tail = new ListNode(value, 0, 0); } else  { head = new ListNode(value, 0, head); head->next->prev = head; } } void List::addToTail(int value) { if (isEmpty()) { head = tail = new ListNode(value, 0, 0); } else  { tail = new ListNode(value, tail, 0); tail->prev->next = tail; } } int List::removeHead() { int value = head->data; if (head == tail) { delete tail; head = tail = 0; } else  { head = head->next; delete head->prev; head->prev = 0; } return value; } int List::removeTail() { int value = head->data; if (head == tail) { delete tail; head = tail = 0; } else  { tail = tail->prev; delete tail->next; tail->next = 0; } return value; } int List::removeAt(int index) { int idx = 0; ListNode* temp = head; while (temp != 0 && idx next; ++idx; } if (temp == 0) exit(1); return removeNode(temp); } bool List::remove(int value) { ListNode* temp = head; while (temp != 0 && temp->data != value) temp = temp->next; if (temp == 0) return false; removeNode(temp); return true; } int List::at(int index) { int idx = 0; const ListNode* temp = head; while (temp != 0 && idx if (temp == 0) exit(1); return temp->data; } int List::valueOf(const ListNode* elem) { return elem->data; } const ListNode* List::getNext(const ListNode* node) { if (node == 0) return 0; return node->next; } const ListNode* List::getPrevious(const ListNode* node) { if (node == 0) return 0; return node->prev; } #endif
 
dij.cpp
 
#include  #include  #include "graph.h" #include "min_heap.h" #include "set.h" #include "stack.h" using namespace std; int main() { Graph g; string path; MinHeap h; cout > path; g.create_graph(path); cout return 0; } 
 
 
 
 
  This assignment involves graphs, and using several different data structures together in order to implement a class graph search algorithm. Dijkastra's Shortest Path Algorithm Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities Source: [ https://en.wikipedia.org/wiki/DIkstra%27s algorithm ] Heap A heap is an ADT that is very similar to the priority-queue from the last assignment. A heap is called a min-heap or a max-heap based on whether smaller or larger values determine the priority of a value. For this assignment, we will be using a min-heap to determine which vertices we want to visit next. You will be using the values in the distance array (see pseudocode) as the priority of a vertex. The min-heap will automatically keep its heap structure when new values are inserted or the min value is extracted from the top. Resources A visual goes a long way in explaining complex algorithms. This video goes through the entire process of Dijkstra's algorithm on the graph that is provided to you in the graph text files Source:[https://www.youtube.com/watch?v 5GTSh YziNoo] Take note of the process and how it related to the pseudocode below. Pseudocode Graph represents the adjacency matrix of a graph. You can determine all of the edges and vertex in the graph just with the adjacency matrix. Source and target are both vertices from the graph, and simply indices from the adjacency matrix.  This assignment involves graphs, and using several different data structures together in order to implement a class graph search algorithm. Dijkastra's Shortest Path Algorithm Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities Source: [ https://en.wikipedia.org/wiki/DIkstra%27s algorithm ] Heap A heap is an ADT that is very similar to the priority-queue from the last assignment. A heap is called a min-heap or a max-heap based on whether smaller or larger values determine the priority of a value. For this assignment, we will be using a min-heap to determine which vertices we want to visit next. You will be using the values in the distance array (see pseudocode) as the priority of a vertex. The min-heap will automatically keep its heap structure when new values are inserted or the min value is extracted from the top. Resources A visual goes a long way in explaining complex algorithms. This video goes through the entire process of Dijkstra's algorithm on the graph that is provided to you in the graph text files Source:[https://www.youtube.com/watch?v 5GTSh YziNoo] Take note of the process and how it related to the pseudocode below. Pseudocode Graph represents the adjacency matrix of a graph. You can determine all of the edges and vertex in the graph just with the adjacency matrix. Source and target are both vertices from the graph, and simply indices from the adjacency matrix