#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
const int inf = 1000; //сокращенное от infinity
const char Universum[] = "abcdefghijklmnopqrstuvwxyz";
const int TIMES = 1e7;
char Ch(const int c) { return c + 'a';}
int length(int a) { return (a==0)?1: log10(a)+1; }
int enter(const int N);
void initGraph(const int N, int** G);
void exe(const int N, int index, int** G, int start, int end, int*, int*, int*);
int main()
{
// srand(time(NULL));
int **G = NULL; //матрица расстояний от каждой вершины до каждой
int N;
int len;
printf("Enter size of graph(<=26): ");
scanf("%d", &N);
while (getchar() != '\n'); //это - лучшая практика
while (N>26 || N<1)
{
printf("Wrong size!\n");
scanf("%d", &N);
while (getchar() != '\n');
}
G = (int**)calloc(N, sizeof(int*));
for (int i=0; i<N; ++i)
G[i] = (int*)calloc(N, sizeof(int));
initGraph(N, G);
int start, end;
double averageTime = 0.0L;
printf("\nEnter start vertex: ");
start = enter(N);
printf("Enter final vertex: ");
end = enter(N);
clock_t startTime = clock();
int* d = (int*)malloc(N * sizeof(int));//минимальное расстояние
int* v = (int*)calloc(N, sizeof(int));//посещенные вершины
int* ver = (int*)malloc(N * sizeof(int));// массив посещенных вершин
len = TIMES - 3;
for (int i = 0; i < len; i += 4){
exe(N, i, G, start, end, d, v, ver);
exe(N, i+1, G, start, end, d, v, ver);
exe(N, i+2, G, start, end, d, v, ver);
exe(N, i+3, G, start, end, d, v, ver);
}
printf("\nTime of %d iterations: %.5lf\n", TIMES, (double)(clock() - startTime) / CLOCKS_PER_SEC);
// printf("\nPress any key to exit\n");
// getch();
for (int i=0; i<N; ++i){
free(G[i]);
}
free(G);
free(d);
free(v);
free(ver);
return 0;
}
//нельзя допустить, чтобы в графе были бессвязные вершины (иначе данные будут недочитываться)
void initGraph(const int N, int** G){
int i, j;
int n = 0; //число вершин
int m = 0; //число ребер
printf("\nMatrix");
for (i=0; i<N+N; ++i)
printf(" ");
printf("Dijkstra\n");
int stringIndex;
char* string = NULL;
string = (char*)malloc(N * sizeof(char));
//цикл "наращивания смежности" (1, если можно попасть, иначе 0)
do{
stringIndex = 0;
// string = (char*)malloc(N * sizeof(char));
memset(string, '\0', sizeof(string));
for (i=0; i<N; ++i)
if (rand()%2 == 0)
string[stringIndex++] = Universum[i];
if (stringIndex == 0){
string[stringIndex++] = Universum[rand()%N];
}
string[stringIndex] = '\0';
for (i = 0; i < stringIndex; ++i){
j = string[i] - 'a';
G[n][j] = 1;
}
++n;
// free(string);
}while(n<N);
free(string);
for (i=0; i<N; ++i)
for (j=0; j<N; ++j)
G[i][j] *= rand()%9 + 1; //наращивание ребер
//умножение на число от 1 до 9, чтобы красиво выводилась таблица
n=m=0;
int f;
for (i=0; i<N; ++i)
{
f = 0;
printf("\n%c: ", Ch(i));
for (j=0; j<N; ++j)
if (G[i][j])
{
++f;
printf("%c ", Ch(j));
}
else printf("- ");
m += f;
if (f) ++n;
else break;
printf(" ");
//вывод нагруженных ребер
for (j=0; j<N; ++j)
printf("%d ", G[i][j]);
}
printf("\n|V| = %d |E| = %d\n", n, m);
}
void exe(const int N, int index, int** G, int start, int end, int* d, int* v, int* ver){
int tmp, minindex, min, i, j;
// int* d = (int*)malloc(N * sizeof(int));//минимальное расстояние
// int* v = (int*)calloc(N, sizeof(int));//посещенные вершины
// int* ver = (int*)malloc(N * sizeof(int));// массив посещенных вершин
int dist;
int vertex;
int len;
for (i=0; i<N; ++i){
d[i] = inf;
v[i] = 0;
ver[i] = 0;
}
d[start] = 0;
do{
minindex = inf;
min = inf;
for (i = 0; i<N; ++i)
{ // if vertex isn't visited and it's weight < min
dist = d[i];
if (!v[i] && dist<min)
{
min = dist;
minindex = i;
}
}
//Sum founded min weight to current weight
if (minindex != inf)
{
for (i = 0; i<N; ++i){
vertex = G[minindex][i];
if (vertex > 0)
{
tmp = min + vertex;
if (tmp < d[i])
d[i] = tmp;
}
}
v[minindex] = 1;
}
}while(minindex < inf);
if (index == TIMES-1){
printf("\nShortest distances to vertices: \n");
for (i = 0; i<N; ++i)
{
printf("%c", Ch(i));
len = length(d[i]);
if (d[i] == inf)
printf(" ");
else for (j=0; j<len; ++j) printf(" ");
}
printf("\n");
for (i = 0; i<N; ++i){
dist = d[i];
if (dist == inf)
printf("- ");
else printf("%d ", dist);
}
printf("\n");
}
//for (int i = 0; i<N; i++) cout << v[i] << ' ';
//Going backwards
ver[0] = end + 1; // идем с конца
int k = 1; // индекс предыдущей вершины
int w = d[end]; // вес конечной вершины
if (w == inf)
{
printf("\nIt's impossible to reach this vertex\n ");
exit(1);
}
while (end != start) // пока не дошли до начальной вершины
{
for (i = 0; i<N; ++i){ // просматриваем все вершины
vertex = G[i][end];
if (vertex != 0) // если связь есть
{
tmp = w - vertex; // определяем вес пути из предыдущей вершины
if (tmp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
w = tmp;
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
++k;
}
}
}
}
if (index == TIMES - 1){
printf("\nOutput of shortest way from %c to %c:\n", Ch(ver[k-1] -1), Ch(ver[0]-1));
for (i = k - 1; i >= 0; --i)
printf("%c ", Ch(ver[i]-1));
}
// free(d);
// free(v);
// free(ver);
}
int enter(const int N)
{
char ch;
scanf("%c", &ch);
while (getchar() != '\n');
while (ch > 'a'+ N - 1 || ch < 'a')
{
printf("Wrong option\n");
scanf("%c", &ch);
while (getchar() != '\n');
}
return ch - 'a';
}
Соседние файлы в папке 1 лаба