Question
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
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
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
void swap_heap_node(int, int);
void min_heapify(int);
public:
MinHeap() { heap = new std::vector
~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
std::cout priority
std::cout
}
#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
for (int c = 0; 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
{
// 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
{
// 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
{
std::cout
exit(1);
}
return adj_matrix[row * adj_matrix_size + column];
}
void Graph::print_adj_matrix()
{
for (int r = 0; r
{
for (int c = 0; c
std::cout
std::cout
}
}
#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 valueOf(temp)
temp = list->getNext(temp);
}
std::cout
}
#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
cin >> path;
g.create_graph(path);
cout
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
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 matrixStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started