Data Structures:

I need to use my implementation of an adjacency list to implement the following methods.

void Graphs_P3::printDijkstra(int source); //prints result of running Dijkstra algorithm with source vertex void Graphs_P3::printGraph(); //prints graph in a format sorted by ascending vertex and edge list

Composition of main() Method (How we Test your code):

Input:

8 - Line 1 indicates the number of operations you will be performing or the number of lines that follow

1 5 - Each line's first integer indicates operation; 1 here means insertVertex() and this follows input to the operation - 5

1 6 - insertVertex(6)

2 5 6 50 - 2 is insertEdge. Therefore, operation is insertEdge(5,6,50)

3 6 5 - 3 is isEdge. Therefore, operation is isEdge(6,5)

4 5 6 - 4 is getWeight. Therefore, operation is getWeight(5,6)

5 5 - 5 is getAdjacent. Therefore, operation is getAdjacent(5)

6 5 - 6 is printDijkstra. Therefore, operation is printDijkstra(5)

7 - 7 is printGraph. Therefore, operation is printGraph()

Output for Dijkstra's Algorithm:

Implement a method to perform Dijkstra's Algorithm to find the shortest path from the source vertex to all other vertices. The output should be a string of the following format

V D P

1 10 0-1

2 8 0-2

3 18 0-1-3

4 25 0-1-3-5-4

5 20 0-1-3-5

The first line is the heading V D P. This stands for vertex, distance, and path. There is a row for each vertex. The row lists the vertex, the distance from the source vertex to that vertex, and path from the source to that vertex.

Here is what I have so far, and as a note the main method cannot be changed but everything else can.

#include #include #include #define MAXSIZE 1000 using namespace std;

class Graphs { private: vector> Vertexes[MAXSIZE]; map index; int size; public: Graphs(); void insertVertex(int vertex); void insertEdge(int from, int to, int weight); bool isEdge(int from, int to); //returns true if there is an edge between the vertices int getWeight(int from, int to); //returns the weight of the edge between the vertices vector getAdjacent(int vertex); //return an array of integers representing vertices adjacent to vertex void printDijkstra(int source); //prints result of running Dijkstra algorithm with source vertex void printGraph(); //prints graph in a format sorted by ascending vertex and edge list };

Graphs::Graphs() { size = 0; } void insertVertex(int vertex) { index[vertex] = size; size++; } void Graphs::insertEdge(int from, int to, int weight) { from = index[from]; Vertexes[from].push_back(make_pair(to,weight)); } bool Graphs::isEdge(int from, int to) //returns true if there is an edge between the vertices from and to { from = index[from]; for(int i=0;i { if(Vertexes[from][i].first == to) { return true; } } return false; } int Graphs_P3::getWeight(int from, int to) //returns the weight of the edge between the vertices from and to { from = index[from]; for(int i=0;i { if(Vertexes[from][i].first == to) { return Vertexes[from][i].second; } } return -1; } vector Graphs_P3::getAdjacent(int vertex) //return an array of integers representing vertices adjacent to vertex { int from = index[vertex]; vector temp; for(int i=0;i { temp.push_back(Vertexes[from][i].first); } return temp; }

void Graphs_P3::printDijkstra(int source); //prints result of running Dijkstra algorithm with source vertex void Graphs_P3::printGraph(); //prints graph in a format sorted by ascending vertex and edge list };

int main() { //DO NOT CHANGE THIS FUNCTION. CHANGE YOUR IMPLEMENTATION CODE TO MAKE IT WORK int noOfLines, operation, vertex, to, fro, weight,source,j; vector arr; int arrSize; Graphs_P3 g; cin>>noOfLines; for(int i=0;i { cin>>operation; switch(operation) { case 1: cin>>vertex; g.insertVertex(vertex); break; case 2: cin>>fro; cin>>to; cin>>weight; g.insertEdge(fro,to,weight); break; case 3: cin>>fro; cin>>to; cout< break; case 4: cin>>fro; cin>>to; cout< break; case 5: cin>>vertex; arr=g.getAdjacent(vertex); arrSize = arr.size(); j=0; while(j>source; g.printDijkstra(source); cout<<" "; break; case 7: g.printGraph(); cout<<" "; break; } } }