For this assignment, you will implement the shortest path algorithm demonstrated
ID: 3766850 • Letter: F
Question
For this assignment, you will implement the shortest path algorithm demonstrated in class (Dijkstra's algorithm). You will take the Graph class I showed you and fill in the shortestPath method. The method should return a vector of node pointers, where each pointer is a stop in the path. For example, if you are finding a path from node A to node E, and the path goes through nodes B, C, and D, in that order, the return value should be a vector whose values are:
[A, B, C, D, E]
NOTE: You'll have to use std:: in front of every ADT you use - std::vector, std::deque, etc.
Starter files:
graph.h - The Graph class, with nothing in the shortestPath method. This is the part you fill in!
main.cpp - A simple file that makes use of the Graph class, including the shortestPath method. This is not a thorough test! Write your own code to test finding paths in more complicated graphs. Make sure you test edge cases (e.g. when a node doesn't exist, when there is no path between the two nodes, etc.).
Things you should understand very well going into this assignment:
Dijkstra's algorithm for finding the shortest path.
Using ADTs - specifically deque, unordered_set, vector, and unordered_map.
Using iterators to go through an ADT one element at a time.
Throwing exceptions.
Templates.
Pointers.
main.cpp contents:
#include "graph.h"
using namespace std;
int main()
{
Graph<string> g;
Node<string>* a = g.insert("a");
Node<string>* b = g.insert("b");
Node<string>* c = g.insert("c");
Node<string>* d = g.insert("d");
Node<string>* e = g.insert("e");
g.connect(a, b);
g.connect(c, d);
g.connect(b, e);
g.connect(c, e);
cout << "Graph 1" << endl;
g.print();
cout << "-----" << endl;
vector<Node<string>*> path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
Graph<string> g2(g);
g2.connect("a", "e");
cout << "Graph 1 again" << endl;
g.print();
cout << "-----" << endl;
cout << "Graph 2" << endl;
g2.print();
cout << "-----" << endl;
path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
path = g2.shortestPath("a", "e");
cout << "Graph 2: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
Graph<string> g3;
g3.insert("z"); // this should get overwritten
g3.insert("y"); // and this
g3.connect("y", "z"); // also this
g3 = g;
g3.connect("a", "e");
cout << "Graph 1 a third time" << endl;
g.print();
cout << "-----" << endl;
cout << "Graph 3" << endl;
g3.print();
cout << "-----" << endl;
path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
path = g3.shortestPath("a", "e");
cout << "Graph 3: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
return 0;
}
And here is graph.h contents:
#ifndef _GRAPH_H
#define _GRAPH_H
#include <cstdlib>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stdexcept>
/*
* Exception for trying to find
* a path between two nodes if
* at least one of the nodes
* doesn't exist.
*/
class NonExistentNodeException : public std::exception
{
public:
virtual const char* what() const throw() {
return "At least one of those nodes doesn't exist!";
}
};
/*
* Exception for trying to find
* a path between two nodes when
* no path exists.
*/
class NoPathException : public std::exception
{
public:
virtual const char* what() const throw() {
return "No path exists between those two nodes!";
}
};
/*
* Node
* -----
* Represents a node in a graph. T is
* the type of value held in the node.
*/
template <typename T>
class Node
{
public:
Node(const T& value) : value(value) {}
/*
* Why wouldn't this do what we want?
*
* Hint: what is the new node connected to?
*/
/*
Node<T>* copy(const Node& other) {
return new Node<T>(value);
}
*/
/*
* Why not a vector for the list of adjacent
* nodes?
*/
std::unordered_set<Node<T>*> adjacents;
T value;
bool marked;
};
/*
* Graph
* -----
* Represents a bi-directional (undirected)
* graph. Nodes can have any value. The
* graph does not have to be connected. Values
* must be unique.
*/
template <typename T>
class Graph
{
public:
Graph() {}
/*
* Since we dynamically allocate each node,
* we need the big 3!
*
* - destructor
* - copy constructor
* - assignment operator
*/
~Graph() {
clear();
}
Graph(const Graph<T>& other) {
copyOther(other);
}
Graph<T>& operator=(const Graph<T>& other) {
if (this != &other) {
clear();
copyOther(other);
}
return *this;
}
/*
* Common graph operations.
*/
Node<T>* insert(const T& value) {
if (nodes.find(value) != nodes.end()) {
return NULL;
}
Node<T>* newNode = new Node<T>(value);
nodes[value] = newNode;
return newNode;
}
// Two versions of connect! One that takes
// node pointers, another that takes node
// values.
void connect(Node<T>* first, Node<T>* second) {
first->adjacents.insert(second);
second->adjacents.insert(first);
}
void connect(const T& first, const T& second) {
if (nodes.find(first) == nodes.end() ||
nodes.find(second) == nodes.end()) {
throw NonExistentNodeException();
}
connect(nodes[first], nodes[second]);
}
void unmarkAll() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
iter->second->marked = false;
}
}
void print() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
std::cout << iter->first << ": ";
for (auto neighborsIter = iter->second->adjacents.begin();
neighborsIter != iter->second->adjacents.end();
neighborsIter++) {
std::cout << (*neighborsIter)->value << " ";
}
std::cout << std::endl;
}
}
std::vector<Node<T>*> shortestPath(const T& start, const T& end) {
// Make sure both nodes exist! If one doesn't, throw
// the appropriate exception.
// Ok, both nodes exist. Get the node pointers from
// your unordered_map!
// You will need some way to store partial paths.
// I highly recommend representing a partial
// path as a vector of node pointers, since this
// is what you will ultimately be returning.
//
// I would ALSO recommend using a deque to store
// all your partial paths. (A deque is
// shorthand for double-ended queue. It's part
// of the STL.
//
// If you choose to use a deque (which you should),
// you'll have a deque of vectors, where each vector
// in turn contains node pointers. Kind of
// complicated! But effective!
// Don't forget to unmark your nodes!
// Your first partial path will just contain one
// node - the start node. Not much of a path, but
// you have to start somewhere!
// Now, repeatedly do the following:
// 1. Get the topmost partial path.
// 2. Look at every node you can get to from
// the end of that partial path (ignoring
// nodes you've already seen).
// 3. Create a partial path that has the same
// nodes as the current partial path, PLUS
// one more node (the node that you're
// looking at).
// 4. Store those partial paths at the end.
//
// You stop when:
// - You see the end node in step 2. Put the
// end node at the end of the current partial
// path, and then return the partial (now
// complete) path!
// - You run out of partial paths to look at.
// If this ever happens, that means there is
// no path to the end node. Throw the
// appropriate exception.
// This method returns an empty vector for now.
// Get rid of this line!
return std::vector<Node<T>*>();
}
private:
std::unordered_map<T, Node<T>*> nodes; // for uniqueness and lookup
void copyOther(const Graph<T>& other) {
for (auto iter = other.nodes.begin();
iter != other.nodes.end();
iter++) {
insert(iter->first);
}
for (auto iter = other.nodes.begin();
iter != other.nodes.end();
iter++) {
auto adjacents = iter->second->adjacents;
for (auto neighborsIter = adjacents.begin();
neighborsIter != adjacents.end();
++neighborsIter) {
// Need to connect the values here!
// Connecting iter->second and *neighborsIter
// would re-connect the nodes in the old graph
// (so this would do nothing)
connect(iter->first, (*neighborsIter)->value);
}
}
}
void clear() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
delete iter->second;
}
nodes.clear();
}
};
#endif
Explanation / Answer
Answer :
#include<iostream>
#include<stdio.h>
using namespace std;
#define SIZE 999
struct node
{
int cost;
int value;
int from;
}a[7];
void min_heap_code(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_heap_code(b, i, n);
}
}
void addEdge(int side[][7], int src, int dest, int cost)
{
side[src][dest] = cost;
return;
}
void sound(int side[][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 = SIZE;
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 (side[temp][k] + a[temp].cost < a[k].cost)
{
a[k].cost = side[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, side[7][7], c = 0, i, j, cost;
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
side[i][j] = SIZE;
}
}
while (c < 12)
{
cout<<"Enter the source, destination and cost of edge ";
cin>>i>>j>>cost;
addEdge(side, i, j, cost);
c++;
}
sound(side);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.