// Memoryless version of Dijkstra's algorithm // See CSE 2320, Notes 14. // This is coded with everything in main() because it is very slow. #include #include typedef enum {s,t} stType; main() { int numVertices,numEdges; int i,j,smallestWeight,smallestEdgeNumber,SPedgeCount; stType *flag; // flag[i] indicates which set vertex i is in. int *vertex1,*vertex2,*weight; // Input tables int *dist; // Distance from vertex 0 for vertices in S scanf("%d %d",&numVertices,&numEdges); flag=(stType*) malloc(numVertices*sizeof(stType)); // Three parallel arrays instead of array of structs vertex1=(int*) malloc(numEdges*sizeof(int)); vertex2=(int*) malloc(numEdges*sizeof(int)); weight=(int*) malloc(numEdges*sizeof(int)); dist=malloc(numVertices*sizeof(int)); if (!flag || !vertex1 || !vertex2 || !weight || !dist) { printf("malloc() failed %d\n",__LINE__); exit(0); } // Get input directed edges. Store in simple tables. for (i=0;inumVertices-1 || vertex2[i]<0 || vertex2[i]>numVertices-1 || weight[i]<=0) { printf("Bad input %d\n",__LINE__); exit(0); } } // Vertex 0 starts in S. Other vertices start in T. flag[0]=s; dist[0]=0; for (i=1;i