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 readonly 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

function Dijkstra(Graph, source, target) distance[source] = 0; create min-heap Q for each vertex v in Graph: if v is not source distance[v] = infinity previous[v] = -1 // * Q.add_with_priority(v, distance[v]) end for while Q is not empty: u = Q.extract_min() if u is target previous[u] = the previous value of u // * break out of while for each neighbor v of u: // only consider v that are still in Q alt = distance[u] + length(u, v) if alt < distance[v] distance[v] = alt previous[v] = u Q.decrease_priority(v, alt) end for end while // Determine the shortest path from source to target using previous array create stack S u = target while previous[u] is defined: push u onto S u = previous[u] push u onto S // Output path ordering with distance between each node // Output total distance of smallest path from source to target end function

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() <= 0; }

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 < size() && (*heap)[lc]->priority < (*heap)[smallest]->priority)

smallest = lc;

if (rc < size() && (*heap)[rc]->priority < (*heap)[smallest]->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 <= size(); ++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 <= size(); ++i)

std::cout << (*heap)[i]->priority << " ";

std::cout << std::endl;

}

#endif

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 < adj_matrix_size; ++r)

for (int c = 0; c < adj_matrix_size; ++c)

adj_matrix[r * adj_matrix_size + c] = 0;

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 < adj_matrix_size; ++r)

{

// get next line of adj matrix

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 < adj_matrix_size; ++c)

{

// fill matrix token by token

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 < 0 || adj_matrix_size <= row || column < 0 || adj_matrix_size <= column)

{

std::cout << "Invalid indexing, no weight exists at " << row << "," << column << std::endl;

exit(1);

}

return adj_matrix[row * adj_matrix_size + column];

}

void Graph::print_adj_matrix()

{

for (int r = 0; r < adj_matrix_size; ++r)

{

for (int c = 0; c < adj_matrix_size; ++c)

std::cout << adj_matrix[r * adj_matrix_size + c] << " ";

std::cout << std::endl;

}

}

#endif

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 << list->valueOf(temp) << " ";

temp = list->getNext(temp);

}

std::cout << std::endl;

}

#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 << "Please enter location of graph file to load: ";

cin >> path;

g.create_graph(path);

cout << g.dimension() << endl;

g.print_adj_matrix();

return 0;

}

graph_1_win.txt

8 0 8 2 5 0 0 0 0 8 0 0 2 0 13 0 0 2 0 0 2 5 0 0 0 5 2 2 0 1 6 3 0 0 0 5 1 0 0 1 0 0 13 0 6 0 0 2 3 0 0 0 3 1 2 0 6 0 0 0 0 0 3 6 0

Outpuut

Please enter location of graph file to load: graph_1_win.txt

Please enter the index of the starting vertex: 0

Please enter the index of the target vertex: 7

The shortest path from vertex 0 to vertex 7 is:

0 to 2: 2

2 to 3: 2

3 to 4: 1

4 to 6: 1

6 to 5: 2

5 to 7: 3

Total path length is 11