What needs to be implemented by you

You are to modify the starter to complete the following tasks:

25 points. To implement dijkstra class method to the Graph class with built-in print utility. Your program shall print out vertex selection sequence and to show the shortest distance between the starting vertex and every vertices in the graph.

The Dijkstra C++ starter with the test driver can be found in the course github

Hint:

If you are overwhelmed by the data structures used for the Dijkstra algorithm, you are not alone. The essential technique to succeed this 210 course is to be able to use existing container as building blocks for solving a complex and/or abstract algorithm, such as the Dijkstra MST.

It has been my experience that more than half of the class run into a wall when trying to make use of multiple containers together, such as a graph (class) that we are constructing.

You may find a test_adj.cpp program on the github that demonstrating a specific implementation of a graph with 4 simple basic containers:

list *adjList; adjList = new list[V]; vectordistance; vectorpicked;

This sample file shows you to add/delete a vertex to/from a graph class implemented with the above containers.

Here is the illustration we did during the lecture on how the Dijkstra algorithm can work with the above data structures:

*The vector visited is the vectorpv in the starter!

Hope the technique used can ease the transition to the technique of container programming if needed.

Expected Output

Your submitted Assignment 10 dijkstra.cpp is expected to generate the following output

Inside the dijkstra class method, you are to output the following information to the console screen:

To print out vertex selection sequence

To show the MST nodes by the picked sequence pair with its distance to the starting vertex.

The output shall appears like the following:

This assignment only expected to complete the edge picking and its proper weight as shown above. The adjacency was illustrated for reference only.

If you have implemented the proper removal of unused edges for the adjacency fix, here is a sample test run on the G4B with some debug trace turned on:

Here's the program that needs to be implemented.

dijkstra.cpp

#include

#include

#include

#include

#include // remove()

#include // INT_MAX

#define ii pair

enum GRAPH_TYPE {DI, BI};

using namespace std;

// functor overloads the compare ii

class compareII {

public:

bool operator()(const ii &j, const ii &k) {

return j.second > k.second;}

};

class Graph

{

int V, E; // No. of vertices, edges

list *adjList; // the djacensy List, alhead pointer to edge list

list *edge; // The edge list from a specific vertex

vector distance; // distances (to starting point) container

vector pv; // picked vertices array

priority_queue, compareII > Q; // type, container, comp

public:

Graph(int v_num) : V(v_num), E(0) {

edge = new list[V];

distance = vector (V, INT_MAX);

}

void addEdge(int u, int v, int w, int type = DI) {

edge[u].push_back(ii(v, w)); E++;

if(type != DI) {

edge[v].push_back(ii(u, w)); E++; }

}

void dijkstra(int v);

void print();

void printGraph();

void printAdjacency();

};

void Graph::printGraph() {

cout

for (auto p : pv) { cout

cout

for (auto p : pv) { cout

cout

for (int n=0; n

cout

cout

}

void Graph::printAdjacency()

{

cout

for (int n = 0; n

cout

for (auto a : adjList[n])

cout ("

cout

}

}

void Graph::dijkstra(int source) {

distance = vector(V, INT_MAX);

distance[source] = 0;

Q.push(ii(source, 0));

adjList = new list[V];

while (!Q.empty()) {

// pop the vertex with smallest distance d of vertex v from Q

// smallest d of v from Q

ii top = Q.top(); Q.pop();

int v = top.first, d = top.second;

// push the selected vertex v into picked vertices array pv

if (d

for (auto e : edge[v]) { // go through all edges e

// if the distance to new node is greater than distance from current node to this node

// replace the distance

// push the new node and distance into the queue

}

}

}

}

// Driver program to test methods of graph class

int main()

{

// Di-graph g(5,10)

Graph g(5);

g.addEdge(0,1,10,DI);

g.addEdge(0,4,5,DI);

g.addEdge(1,2,1,DI);

g.addEdge(1,4,2,DI);

g.addEdge(1,3,4,DI);

g.addEdge(3,0,7,DI);

g.addEdge(3,2,6,DI);

g.addEdge(4,1,3,DI);

g.addEdge(4,2,9,DI);

g.addEdge(4,3,2,DI);

cout

g.dijkstra(0);

g.printGraph();

cout

g.printAdjacency();

// Bidirection G2B (9,28)

Graph G2B(9);

G2B.addEdge(0,1,4,BI);

G2B.addEdge(0,7,8,BI);

G2B.addEdge(1,2,8,BI);

G2B.addEdge(1,7,11,BI);

G2B.addEdge(2,3,7,BI);

G2B.addEdge(2,5,4,BI);

G2B.addEdge(2,8,2,BI);

G2B.addEdge(3,4,9,BI);

G2B.addEdge(3,5,14,BI);

G2B.addEdge(4,5,10,BI);

G2B.addEdge(5,6,2,BI);

G2B.addEdge(6,7,1,BI);

G2B.addEdge(6,8,6,BI);

G2B.addEdge(7,8,7,BI);

cout

G2B.dijkstra(2);

G2B.printGraph();

cout

G2B.printAdjacency();

Graph G3B(6);

G3B.addEdge(0,1,2,BI);

G3B.addEdge(0,2,3,BI);

G3B.addEdge(1,2,2,BI);

G3B.addEdge(1,3,6,BI);

G3B.addEdge(2,3,2,BI);

G3B.addEdge(2,4,3,BI);

G3B.addEdge(3,4,2,BI);

G3B.addEdge(3,5,6,BI);

G3B.addEdge(4,5,2,BI);

cout

G3B.dijkstra(2);

G3B.printGraph();

cout

G3B.printAdjacency();

// 2 3

// (0)--(1)--(2)

// | / \ |

// 6| 8/ \5 |4

// | / 1 \ |

// (3)-------(4)

Graph G4B(5);

G4B.addEdge(0,1,2,BI);

G4B.addEdge(0,3,6,BI);

G4B.addEdge(1,2,3,BI);

G4B.addEdge(1,3,8,BI);

G4B.addEdge(1,4,5,BI);

G4B.addEdge(2,4,4,BI);

G4B.addEdge(3,4,1,BI);

cout

G4B.dijkstra(1);

G4B.printGraph();

cout

G4B.printAdjacency();

return 0;

}

distamce xad lis+ ? 0712313.8 42 2 2 4 evt neyt mme diat edges distamce xad lis+ ? 0712313.8 42 2 2 4 evt neyt mme diat edges