程序代写代做代考 graph algorithm //HW4A: Dijkstra’s algorithm with HEAP

//HW4A: Dijkstra’s algorithm with HEAP
//HW4B: Use the same design for Prim’s algorithm
//For each x->y edges, also create a y->x edge with the same weight
//HW4A Due: Friday Oct. 2; HW4B Due: Tuesday, Oct. 6
//Complexity: O((N+E) log N)
#include
#include
#include using namespace std;

class Node {
public:
int cost; //cost to a node
int from; //the from node to this node
bool checked;
int h_index; //the index in heap for this node
Node() : cost(9999), from(-1), checked(false), h_index(-1) {}
};

void Path(vector>>& graph, vector& table, vector& heap);//HW4A
//You can create up to two help functions for Path
void MST(vector>>& graph, vector& table, vector& heap); //HW4B
//You can create up to two help functions for MST
int main() {

vector>> graph;
//your code to read in graph from “graph.txt”
vector table;
vector heap;
//You might need to make some setting for table and heap
Path(graph, table, heap);//HW4A
MST(graph, table, heap);//HW4B
//print results
}
void Path(vector>>& graph, vector& Table, vector& heap) {

//Your code — HW4A 32 pts
}
void MST(vector>>& graph, vector& table, vector& heap) {

//Your code — HW4B 13 pt
}

/*
The following screenshot might not be a correct run. It shows the required output format.

//sample screenshot for Dijkstra’s algorithm
cost from 0 to 0 is : 0 from node is 0 Path: 0
cost from 0 to 1 is : 7 from node is 2 Path: 1<-2<-0 cost from 0 to 2 is : 4 from node is 0 Path: 2<-0 cost from 0 to 3 is : 10 from node is 1 Path: 3<-1<-2<-0 cost from 0 to 4 is : 14 from node is 3 Path: 4<-3<-1<-2<-0 cost from 0 to 5 is : 9 from node is 1 Path: 5<-1<-2<-0 */ /* //sample input file graph.txt 0 //source code 6 //# of nodes in graph 12 //# of edges in graph 0 5 16//an edge from node 0 to node 5 with a weight (cost) of 16 0 4 15 0 2 4 0 3 12 0 1 9 1 3 3 1 5 2 2 3 14 2 1 3 3 4 4 4 5 1 5 3 2 */ /* //sample screenshot for Prim's algorithm; 1 2 3 is the same as 2 1 3 1 2 3 2 0 4 3 5 2 4 5 1 5 1 2 The overall cost is 12. */