Введение графа. Нахождение и выведение кратчайшего пути из одной вершины в другую, страница 2

int count(stack *s) // счёт количества ходов в стеке

{

    int num = 0;

    while (s->pr != NULL)    // пока стек не пуст

               {

        num ++;              // наращиваем счётчик

        s = s->pr;

    }

    return num;

}

int check(stack *head)       // проверка не было ли на этой вершине ранее

{ 

    stack *s = head->pr;     // пока стек не пуст 

    while (s != NULL)

               {

        if (s->numb == head->numb) return 1;   // если вершины совпадют возвращаем истину

        s = s->pr;

    }

    return 0;

}

stack* minway(stack *s, int numb)   // поиск минимального пути

{             

    stack *nw;

    stack* min = NULL;

    int tmp_int;                      

    stack *tmp_st;

    int i;

    nw = (stack *) calloc(1, sizeof(stack));     // буфер

    nw->numb = numb;

    nw->pr = s;

    if (nw->numb == end) return nw;              // если текущая вершина совпадает с конечной, то путь

                                                                                 // (не обязательно конечный) найден

    if (check(nw) != 0)

               {                                                                 // если на текущей вершине уже находились,

        free(nw);                                                        // то этот путь не может быть кратчайшим,

        return NULL;                                                  // поэтому дальше не идём и возвращаем NULL

    }

    for (i = 1; i < n + 1; i++)                                // перебор вершин

        if (m[nw->numb][i] != 0)

                              {                                                   // если из текущей вершины есть переход в i-тую

            tmp_st = minway(nw, i);                 // то запускаем функцию снова

            if (tmp_st == NULL) continue;

            tmp_int = count(tmp_st);

            if (tmp_int != -1 && (min == NULL || tmp_int < count(min))) min = tmp_st;

        }                                                                                                                                         

        return min;                              // возвращаем минимальное количество ходов

}

void course(stack *h)

{

    if (h->pr) course(h->pr);              // выводим стек в обратном порядке

    printf("%d\t", h->numb);

}

void output(stack *h)  //вывод количества шагов

{

    if (h == NULL)

               {

        puts("Введите вершины корректно!");

        return;

    }

    printf("Минимальное количество шагов: %d\n", count(h));

    course(h);

}

int main()

{

    int i;

    int a, b;

    setlocale(LC_ALL , ".1251");

    do

               {

        printf("Введите количество вершин: ");  // ввод количества вершин

        scanf("%d", &n);

    }

               while (n <= 0);

    m = (int**) malloc((n + 1)*sizeof(int*));   // создание матрицы переходов

    for (i = 0; i < n + 1; i++) m[i] = (int*)calloc(n + 1, sizeof(int));

    puts("Введите переходы между вершинами (0 - признак конца ввода)");

    do

               {

        scanf("%d %d", &a, &b);                             // ввод переходов между вершинами

        if (a >= 0 && a <= n && b >= 0 && b <=n) m[a][b] = m[b][a] = 1;

        else puts("Введены некорректные вершины");

    }

               while (a != 0);

    do                                                   // задание начальной точки

               {

        puts("Введите начальную вершину");

        scanf("%d", &a);

    }

               while (a < 1 || a > n);

    do

               {

        puts("Введите конечную вершину");                // задание конечной точки

        scanf("%d", &end);

    }

               while (end < 1 || end > n);

    output(minway(NULL, a));                             // поиск мин. пути

    getch();

    return 0;

}

Результат выполнения программы