// Dijkstra's Algorithm in C using a heap with the best S vertex for // every T vertex. // See CSE 2320 Notes 14 #include #include #include "minHeap.h" using namespace std; // For getrusage() #include #include // Basic Definitions #define oo (1000000000) // Declarations int numVertices,numEdges; struct edge { int tail,head,weight; int next; // subscript of next edge with same tail }; typedef struct edge edgeType; edgeType *edgeTab; int *firstEdge; // Table indicating first edge for a tail float CPUtime() { struct rusage rusage; getrusage(RUSAGE_SELF,&rusage); return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0 + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0; } void read_input_file() { // Reads a file with a weighted, directed graph and // stores as unordered adjacency lists. int tail,head,weight,i,j,workingEdges; // read number of nodes and edges cin >> numVertices >> numEdges; firstEdge=(int*) malloc(numVertices*sizeof(int)); edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType)); if (!firstEdge || !edgeTab) { cout << "edgeTab malloc failed " << __LINE__ << "\n"; exit(0); } // Initially, all adjacency lists are empty for (i=0;i> tail >> head >> weight; // Test for illegal edge. if (tail<0 || tail>numVertices-1 || head<0 || head>numVertices-1 || weight<=0) { cout << "Invalid input " << tail << head << weight << " at " << __LINE__ << "\n"; exit(0); } // Save input edge and insert in adjacency list edgeTab[workingEdges].tail=tail; edgeTab[workingEdges].head=head; edgeTab[workingEdges].weight=weight; edgeTab[workingEdges].next=firstEdge[tail]; firstEdge[tail]=workingEdges; workingEdges++; } } void dijkstra() { typedef enum {s,t} stType; int i,j,SPedgeCount=0; stType *flag; heapEntryType smallest,changing; int *priority,*bestSneighbor; flag=(stType*) malloc(numVertices*sizeof(stType)); priority=(int*) malloc(numVertices*sizeof(int)); bestSneighbor=(int*) malloc(numVertices*sizeof(int)); if (!flag || ! priority || !bestSneighbor) { cout << "malloc failed " << __LINE__ << "\n"; exit(0); } // Vertex 0 starts in S. Other vertices start in T. flag[0]=s; for (i=1;i