//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
//You can create up to two help functions for Path
void MST(vector
//You can create up to two help functions for MST
int main() {
vector
//your code to read in graph from “graph.txt”
vector
vector
//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
//Your code — HW4A 32 pts
}
void MST(vector
//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.
*/