Описание программы

#include <iostream> #include <stdlib.h> #include <conio.h> #include <time.h> #include <chrono> #include <fstream> #define k1 3 #define INT_MAX 9999999 using namespace std; using namespace chrono; void floyd(int** mtx, int size) { for (int k = 0; k < size; k++) for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) if (mtx[k][j] + mtx[i][k] < mtx[i][j]) mtx[i][j] = mtx[k][j] + mtx[i][k]; } int *Dijkstra(int **GR, int V, int st) { int *distance, count, index, i, u; bool *visited; distance = new int [V]; visited = new bool [V]; for (i=0; i<V; i++) { distance[i]=INT_MAX; visited[i]=false; } distance[st]=0; for (count=0; count<V-1; count++) { int min=INT_MAX; for (i=0; i<V; i++) if (!visited[i] && distance[i]<=min) { min=distance[i]; index=i; } u=index; visited[u]=true; for (i=0; i<V; i++) if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX && distance[u]+GR[u][i]<distance[i]) distance[i]=distance[u]+GR[u][i]; } delete [] distance; delete [] visited; return distance; } void get_random_graph(int** graph, int size) { for(int i = 0; i < size; i++) graph[i][i] = 0; for(int i = 0; i < size; i++) for(int j = 0; j < size; j++) if(i != j) { int weight = 1 + (rand() % 13); graph[i][j] = graph[j][i] = (weight < 10) ? (static_cast<double>(weight)) : (9999); } } int main() { chrono::nanoseconds totalTime1st; totalTime1st=totalTime1st-totalTime1st; chrono::nanoseconds totalTime2; totalTime2=totalTime2-totalTime2; long times = 1000; int stepcount = 20; cout << "Rekomenduetsya vvodit chislo ot 1000\n"; cout << "vvedite kolichestvo povtornih zapuskov: "; cin >> times; float *krask_av = new float[stepcount]; float *prim_av = new float[stepcount]; int size = 4; for (int i=1; i<=stepcount; i++) { size += k1; cout << "mtx size = " << size << endl; int **mtx3 = new int* [size]; for (int k = 0; k < size; k++) mtx3[k] = new int [size]; int **mtx2 = new int* [size]; for (int k = 0; k < size; k++) mtx2[k] = new int [size]; get_random_graph(mtx3, size); file_print(mtx3, size); for (int k; k<size; k++) for (int d; d<size;d++) mtx2[k][d]=mtx3[k][d]; for (int j=1; j<=times; j++) { for (int k; k<size; k++) for (int d; d<size;d++) mtx3[k][d]=mtx2[k][d]; system_clock::time_point start = chrono::system_clock::now(); floyd(mtx3, size); system_clock::time_point end = chrono::system_clock::now(); file_print(mtx3, size); chrono::nanoseconds elapsedSeconds = end-start; totalTime1st += elapsedSeconds; int *dist = new int [size]; start = chrono::system_clock::now(); dist = Dijkstra(mtx2,size,1); end = chrono::system_clock::now(); elapsedSeconds = end-start; totalTime2 += elapsedSeconds; } totalTime1st/=(times); krask_av[i-1]=totalTime1st.count(); totalTime1st=totalTime1st-totalTime1st; totalTime2/=(times); prim_av[i-1]=totalTime2.count(); totalTime2=totalTime2-totalTime2; for (int k = 0; k < size; k++) delete [] mtx3[k]; } ///Вывод---------------------------------------------------------------------/// cout << "\tfloyd alg\tdijkstra alg\n"; fstream fout ("rez.txt", ios::out); for (int i=1; i<=stepcount; i++) { printf("\t %7.2f \t %7.2f\n" , krask_av[i-1], prim_av[i-1]); fout << krask_av[i-1] << "\t" << prim_av[i-1] << endl; } fout.close(); delete [] krask_av; delete [] prim_av; getch(); return 0; }