Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- // Чтение графа происходит из файла in.txt, который устроен следующим образом
- // Сначала идут три целых числа: n - количество вершин, a - пункт отправления, b - пункт назначения
- // Затем идет n строк по n целых чисел в каждой строке - матрица смежности графа
- // Запись осуществляется в файл out.txt
- unsigned const int MAX_SIZE = 100;
- void read_graph(int * graph, int * n, int * a, int * b, const char * filename);
- int search_path(int * graph, int n, int a, int b, int * path, int * path_len);
- void write_path(int * path, int n, int dist, const char * filename);
- int pop(int * queue, int * n);
- void push(int * queue, int * n, int value);
- int main(){
- int graph[MAX_SIZE][MAX_SIZE]; // Матрица смежности графа
- int n, a, b, d; // n - количество вершин. Из вершины a в вершину b ищем минимальный путь. d - величина минимального пути
- int path[MAX_SIZE]; // Путь
- int path_len; // Его длина
- int * ptr_graph = (int*)graph; // Указатель на матрицу смежности
- read_graph(ptr_graph, &n, &a, &b, "in.txt"); // Считываем граф
- if (d = search_path(ptr_graph, n, a, b, path, &path_len)) // Ищем путь
- printf("The path has been successfully found!\n");
- else
- printf("The right path does not exist!\n");
- write_path(path, path_len, d, "out.txt"); // Записываем путь в файл
- return 0;
- }
- void read_graph(int * graph, int * n, int * a, int * b, const char * filename){
- // Открываем файл для чтения:
- FILE *fp;
- fp = fopen(filename, "r");
- // Считываем оттуда количество вершин, вершину a и вершину b:
- fscanf(fp, "%d %d %d", n, a, b);
- // Считываем оттуда матрицу смежности графа:
- int i, j;
- for (i = 0; i < *n; i++)
- for (j = 0; j < *n; j++)
- fscanf(fp, "%d ", graph+(*n)*i+j);
- // Закрываем файл
- fclose(fp);
- }
- int pop(int * queue, int * n){
- // Вынимаем элемент из очереди
- int t = queue[0], i;
- *n -= 1;
- for(i = 0; i < *n; i++)
- queue[i] = queue[i+1];
- return t;
- }
- void push(int * queue, int * n, int value){
- // Кладем новый элемент в очередь
- queue[*n] = value;
- *n += 1;
- }
- int search_path(int * graph, int n, int a, int b, int * path, int * path_len){
- // Ищем минимальный путь поиском в ширину
- *path_len = 0; // Длина пути
- int visited[MAX_SIZE], q[MAX_SIZE], distance[MAX_SIZE]; // Посещенные вершины и очередь для посещения вершин
- int q_len = 0, i, j; // Длина очереди и счетчики циклов
- // distance[i] будет хранить величину кратчайшего пути , который мы прошли из стартовой вершины в вершину i
- for(i = 0; i < n; i++){ // Обнуляем массив посещенны вершин
- visited[i] = -1;
- distance[i] = 0;
- }
- // Кидаем стартовую вершину в очередь и запоминаем, что мы ее посетили:
- push(q, &q_len, a);
- visited[a] = a;
- // Пока мы не обработали необходимые вершины, обрабатываем их:
- while (q_len > 0) {
- // Вынимаем очередную вершину:
- const int t = pop(q, &q_len);
- // Если мы достигли необходимой вершины, то логично бы прекратить поиск
- if (t == b) break;
- // В цикле кидаем в очередь все непосещенные смежные с вершиной t вершины:
- for (i = 0; i < n; i++)
- // ЕСЛИ существует ребро t -> i И мы не входим в вершину а И ЛИБО вершина i еще не была посещена , ЛИБО посещена не самым кратчайшим путём
- if (*(graph+t*n+i) && i != a && (distance[i] == 0 || distance[t] + *(graph+t*n+i) < distance[i])) {
- distance[i] = distance[t] + *(graph+t*n+i); // Сохраняем пройденную дистанцию
- visited[i] = t; // Сохраняем в visited[i] вершину t, из которой мы пришли в вершину i
- push(q, &q_len, i); // Кидаем вершину i в очередь обработки
- }
- }
- // Величина найденного кратчайшего пути a -> b :
- int d = distance[b];
- // Возвращаемся из вершины b в вершину a по тому пути , который мы запомнили в visited
- while ( b != a && visited[b] != -1 ){
- push(path, path_len, b); // Кидаем вершины в вектор пути
- b = visited[b];
- }
- // Если нам удалось дойти до стартовой вершины , то кидаем ее в наш путь
- if ( b == a ) push(path, path_len, a);
- // Приведение пути к нормальному виду (переворачиваем его)
- for (i = 0, j = *path_len-1; i < j; ++i,--j){
- int temp = path[i];
- path[i] = path[j];
- path[j] = temp;
- }
- return d; // Возвращаем длину найденного пути
- }
- void write_path(int * path, int n, int dist, const char * filename){
- // Запись пути в файл
- FILE *fp;
- fp = fopen(filename, "w");
- int i;
- fprintf(fp, "%d\n", dist);
- for (i = 0; i < n; i++)
- fprintf(fp, "%d ", path[i]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement