This question may take some time to answer, I only want answers from readers who
ID: 666908 • Letter: T
Question
This question may take some time to answer, I only want answers from readers who show that they spent their time on this homework. This is the third time I am asking the same question. Will only thumbs up if the reader follows directions. Thanks.
USE THE METHODS PROVIDED PLEASE!
After hearing about Dijkstra's algorithm, Fred wants to investigate how using different types of priority queues affects the run time on different types of graphs. In particular he wants to investigate the difference between a binary heap priority queue and an unsorted array priority queue. He has already written the unsorted array priority queue, but needs you to implement the binary heap and Dijkstra's algorithm.
In the test data, the numbers 0 to n-1 will represent our vertices and each edge will have a cost in the range 1 to 10. We represent the graph in the code using an adjacency list structure of a vector of vectors of (int,int) pairs. If the i-th vector has a pair of (j,k), then this corresponds to an edge from i to j of cost k.
The starter code for this project consists of three files: main.cpp, pq_unsorted_array.hpp, and pq_binary_heap.hpp. The main.cpp file parses out a graph from a data file and calls a method dijkstra() to find the shortest distance between two of the points. You are responsible for finishing the implementation of Dijkstra's algorithm. The pq_unsorted_array.hpp file is a priority queue implementation using an unsorted array. It is provided for you and you are not required to change any of its code. The pq_binary_heap.hpp file contains the method stubs for the binary heap you will be implementing.
Your final handin code should have dijkstra() using your binary heap implementation.
I need help implementing the dijkstra's algorithm for the PQUnsortedArray and need to define the methods in the binary heap. Please write down comments so I can follow the thinking process and learn the ideas behind the code.
USE THE METHODS PROVIDED PLEASE!
Begin Code:
main.cpp
// ICS/CSE 46 Summer 2015
// Project 4
//
// This file parses the data file and builds the corresponding
// graph. You are responsible for implementing dijkstra().
//
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <ctime>
#include "pq_unsorted_array.hpp"
//#include "pq_binary_heap.hpp"
// Returns the distance from the vertex start to the vertex end
// in the graph using dijkstra's algorithm
//
// The graph is provided in the form of an adjacency list
// Each vertex is a number from 0 to n-1
// The i-th vector in graph consists of pairs which correspond
// to edges in the graph. The first item of each pair is the
// neighboring vertex and the second item is the cost to
// follow that edge.
int dijkstra(std::vector<std::vector<std::pair<int,int>>> graph,
int start, int end)
{
// Initializes a priority queue and map
PQUnsortedArray<int,int> pq;
std::unordered_map<int,int> best_so_far;
for (int i = 0; i < graph.size(); i++)
{
// We use INT_MAX to represent infinity
//initialize all elements to have infinity in PQ and the unorderedmap
pq.insert(INT_MAX,i);
best_so_far[i] = INT_MAX;
}
//begin by updating the start to have value 0
pq.update(0,start);
best_so_far[start] = 0;
//TODO: finish implementing this method
throw std::logic_error("Dijkstra's algorithm should never reach the end of the function");
}
int main()
{
// Read in a filename containing a graph
std::cout<<"Which file do you want to look at? ("dense", "sparse", or "simple")"<<std::endl;
std::string name;
std::cin>>name;
std::string file_name = "data/"+name+".txt";
std::ifstream in_file(file_name);
// Parse the number of vertices out of the file
std::string line;
std::getline(in_file,line);
int n = std::stoi(line);
// Reserve the appropriate amount of space for our adjacency list
std::vector<std::vector<std::pair<int,int>>> graph;
graph.reserve(n);
// Initialize the n vectors for the adjacency list
for (int i = 0; i < n; i++)
graph.push_back(std::vector<std::pair<int,int>>());
// Parse the edges out of the text file
while(std::getline(in_file,line))
{
std::string::size_type first_comma = line.find(",");
std::string::size_type second_comma = line.find(",",first_comma+1);
int from = std::stoi(line.substr(0,first_comma));
int to = std::stoi(line.substr(first_comma+1,second_comma));
int cost = std::stoi(line.substr(second_comma+1));
graph[from].push_back(std::pair<int,int>(to,cost));
}
// Read in two vertices to find the shortest path between
std::cout<<"Pick a start vertex: (A number in the range 0 to "<<(n-1)<<")"<<std::endl;
int start;
std::cin>>start;
std::cout<<"Pick an end vertex: (A number in the range 0 to "<<(n-1)<<")"<<std::endl;
int end;
std::cin>>end;
// Run dijkstra() and output the distance computed and the runtime
auto start_time = clock();
int distance = dijkstra(graph,start,end);
auto stop_time = clock();
double time = 1000 * static_cast<double>(stop_time - start_time) / CLOCKS_PER_SEC;
std::cout<<"The distance from "<<start<<" to "<<end<<" is "<<distance<<std::endl;
std::cout<<"Time: "<<time<<" (ms)"<<std::endl;
return 0;
}
//end main.cpp
pq_unsorted_array.hpp
// ICS/CSE 46 Summer 2015
// Project 4
//
// This file contains an implementation of a priority queue using
// an unsorted array. You do not need to edit this code.
// You may find it useful to understand this code when writing
// your binary heap class.
//
// It is recommended that you implement dijkstra using this
// priority queue first before switching to your binary heap.
//
#ifndef __PQ_UNSORTED_ARRAY_HPP__
#define __PQ_UNSORTED_ARRAY_HPP__
#include <unordered_map>
#include <stdexcept>
#define INITIAL_CAPACITY 10
template <class K, class V>
class PQUnsortedArray {
public:
// Default constructor: creates an empty priority queue
PQUnsortedArray();
// Destructor: deallocates all memory associated
// with the priority queue
~PQUnsortedArray();
// size() returns the number of elements currently
// stored in the priority queue
unsigned int size() const;
// insert() adds an element to the priority queue
void insert(const K& key, const V& value);
// remove_minimum() returns the value whose associated
// key is the smallest
std::pair<K,V> remove_minimum();
// update() updates the key associated with value to be
// equal to new_key
void update(const K& new_key, const V& value);
private:
// The array storing the key value pairs
std::pair<K,V>* array;
// num_elements and capacity help keep track of how much
// of the array is being used
unsigned int num_elements;
unsigned int capacity;
// A private resize function for when we have filled up the array
void resize();
// A map keeping track of the array positions for each element
std::unordered_map<V,int> lookup_map;
};
template <class K, class V>
PQUnsortedArray<K,V>::PQUnsortedArray()
{
array = new std::pair<K,V>[INITIAL_CAPACITY];
lookup_map = std::unordered_map<V,int>();
num_elements = 0;
capacity = INITIAL_CAPACITY;
}
template <class K, class V>
PQUnsortedArray<K,V>::~PQUnsortedArray()
{
delete array;
}
template <class K, class V>
unsigned int PQUnsortedArray<K,V>::size() const
{
return num_elements;
}
template <class K, class V>
void PQUnsortedArray<K,V>::insert(const K& key, const V& value)
{
if (num_elements == capacity)
resize();
lookup_map[value]=num_elements;
array[num_elements] = std::pair<K,V>(key,value);
num_elements++;
}
template <class K, class V>
std::pair<K,V> PQUnsortedArray<K,V>::remove_minimum()
{
if (num_elements == 0)
throw std::runtime_error("Cannot remove minimum from an empty priority queue");
// Iterate through the array to find the min
K min_key = array[0].first;
int min_index = 0;
for (int i = 1; i < num_elements; i++)
{
if (array[i].first < min_key)
{
min_key = array[i].first;
min_index = i;
}
}
std::pair<K,V> min = array[min_index];
// Shift over the other key value pairs
for (int i = min_index+1; i < num_elements; i++)
{
array[i-1] = array[i];
lookup_map[array[i-1].second] = i-1;
}
num_elements--;
return min;
}
template <class K, class V>
void PQUnsortedArray<K,V>::update(const K& new_key, const V& value)
{
if (lookup_map.count(value) == 0)
throw std::runtime_error("Cannot update a value not in the priority queue");
int index = lookup_map[value];
array[index] = std::pair<K,V>(new_key,value);
}
template <class K, class V>
void PQUnsortedArray<K,V>::resize()
{
std::pair<K,V>* old_array = array;
//Create a new array with double the capacity
capacity*=2;
array = new std::pair<K,V>[capacity];
// Copy over the key value pairs
for (int i = 0; i < num_elements; i++)
array[i] = old_array[i];
delete old_array;
}
#endif // __PQ_UNSORTED_ARRAY_HPP__
end pq_unsorted_array.hpp
pq_binary_heap.hpp
// Project 4
//
// This file contains method stubs for a priority queue using
// a binary heap. You are responsible for implementing the
// method stubs.
//
// It is recommended that you implement dijkstra using the
// unsorted array priority queue first before switching to
// your binary heap.
//
#ifndef __PQ_BINARY_HEAP_HPP__
#define __PQ_BINARY_HEAP_HPP__
#include <unordered_map>
#include <stdexcept>
#define INITIAL_CAPACITY 10
template <class K, class V>
class PQBinaryHeap {
public:
// Default constructor: creates an empty priority queue
PQBinaryHeap();
// Destructor: deallocates all memory associated
// with the priority queue
~PQBinaryHeap();
// size() returns the number of elements currently
// stored in the priority queue
unsigned int size() const;
// insert() adds an element to the priority queue
void insert(const K& key, const V& value);
// remove_minimum() returns the key value pair whose
// associated key is the smallest
std::pair<K,V> remove_minimum();
// update() updates the key associated with value to be
// equal to new_key
void update(const K& new_key, const V& value);
private:
// The array storing the key value pairs as an implicit
// complete binary tree
std::pair<K,V>* heap;
// num_elements and capacity help keep track of how much
// of the array is being used
unsigned int num_elements;
unsigned int capacity;
// A private resize function for when we have filled up the array
void resize();
// A map keeping track of the array positions for each element
std::unordered_map<V,int> lookup_map;
};
template <class K, class V>
PQBinaryHeap<K,V>::PQBinaryHeap()
{
//TODO: implement this method
}
template <class K, class V>
PQBinaryHeap<K,V>::~PQBinaryHeap()
{
//TODO: implement this method
}
template <class K, class V>
unsigned int PQBinaryHeap<K,V>::size() const
{
//TODO: implement this method
}
template <class K, class V>
void PQBinaryHeap<K,V>::insert(const K& key, const V& value)
{
//TODO: implement this method
}
template <class K, class V>
std::pair<K,V> PQBinaryHeap<K,V>::remove_minimum()
{
//TODO: implement this method
}
template <class K, class V>
void PQBinaryHeap<K,V>::update(const K& new_key, const V& value)
{
//TODO: implement this method
}
template <class K, class V>
void PQBinaryHeap<K,V>::resize()
{
//TODO: implement this method
}
#endif // __PQ_BINARY_HEAP_HPP__
end pq_binary_heap.hpp
Thank you for taking your time to read my code, I look forward to your helpful response.
USE THE METHODS PROVIDED PLEASE!
Explanation / Answer
Dijkastra Algo using Priority Queue:
#include<iostream>
#include<stdio.h>
using namespace std;
#include<conio.h>
#define INFINITY 999
struct node
{
int cost;
int value;
int from;
}a[7];
void min_heapify(int *b, int i, int n)
{
int j, temp;
temp = b[i];
j = 2 * i;
while (j <= n)
{
if (j < n && b[j + 1] < b[j])
{
j = j + 1;
}
if (temp < b[j])
{
break;
}
else if (temp >= b[j])
{
b[j / 2] = b[j];
j = 2 * j;
}
}
b[j / 2] = temp;
return;
}
void build_minheap(int *b, int n)
{
int i;
for(i = n / 2; i >= 1; i--)
{
min_heapify(b, i, n);
}
}
void addEdge(int am[][7], int src, int dest, int cost)
{
am[src][dest] = cost;
return;
}
void bell(int am[][7])
{
int i, j, k, c = 0, temp;
a[0].cost = 0;
a[0].from = 0;
a[0].value = 0;
for (i = 1; i < 7; i++)
{
a[i].from = 0;
a[i].cost = INFINITY;
a[i].value = 0;
}
while (c < 7)
{
int min = 999;
for (i = 0; i < 7; i++)
{
if (min > a[i].cost && a[i].value == 0)
{
min = a[i].cost;
}
else
{
continue;
}
}
for (i = 0; i < 7; i++)
{
if (min == a[i].cost && a[i].value == 0)
{
break;
}
else
{
continue;
}
}
temp = i;
for (k = 0; k < 7; k++)
{
if (am[temp][k] + a[temp].cost < a[k].cost)
{
a[k].cost = am[temp][k] + a[temp].cost;
a[k].from = temp;
}
else
{
continue;
}
}
a[temp].value = 1;
c++;
}
cout<<"Cost"<<" "<<"Source Node"<<endl;
for (j = 0; j < 7; j++)
{
cout<<a[j].cost<<" "<<a[j].from<<endl;
}
}
int main()
{
int n, am[7][7], c = 0, i, j, cost;
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
am[i][j] = INFINITY;
}
}
while (c < 12)
{
cout<<"Enter the source, destination and cost of edge ";
cin>>i>>j>>cost;
addEdge(am, i, j, cost);
c++;
}
bell(am);
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.