Lab 4 v0.9

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>

int main()
{
    unsigned int N, nu, action;
    unsigned int i, j, tmp;
    int *matrix = NULL;

    printf("Matrix from keyboard - 1, from file - 2: ");
    scanf("%d", &action);
    if(action == 1)
    {
        printf("Enter amount of vertexes: ");
        scanf("%d", &N);
        N = 5;
        matrix = (int *)malloc(N * N * sizeof(int)); //Матрица смежности

        for (i = 0; i < N; i++)
        {
            for (j = 0; j < N; j++)
            {
                if (i != j)
                {
                    printf("Route frome vertex %d to vertex %d is: ", i + 1, j + 1);
                    scanf("%d", &tmp);
                    if (tmp == 0)
                    {
                        tmp = 10000; //Принимаем за бесконечность
                    }
                }
                else
                    tmp = 10000;
                matrix[i * N + j] = tmp;
            }
        }
    }
    else if (action == 2)
    {
        FILE *in;
        if ((in = fopen("C:\\test\\graph.txt", "rt")) == NULL)
        {
            printf("Could not open file");
            return -1;
        }
        fscanf(in, "%d", &N);
        matrix = (int *)malloc(N * N * sizeof(int)); //Матрица смежности

        for (i = 0; i < N; i++)
        {
            for (j = 0; j < N; j++)
            {
                fscanf(in, "%d", &tmp);
                if (tmp == 0)
                {
                    tmp = 10000; //Принимаем за бесконечность
                }
                matrix[i * N + j] = tmp;
            }
        }
        fclose(in);
    }

    //Алгоритм Дейскстры
    printf("Enter target vertex: ");
    scanf("%d", &tmp);
    nu = tmp - 1;

    int *S = (int *)calloc(N, sizeof(int)); //Массив просмотренных вершин
    int *D = (int *)malloc(N * sizeof(int)); //Массив кратчайших расстояний

    S[nu] = 1; //Первая вершина
    for (j = 0; j < N; j++)
    {
        if (j == nu)
        {
            D[j] = 0;
            continue;
        }
        D[j] = matrix[j];
    }

    for (i = 0; i < N; i++)
    {
        tmp = find_min_positive(D, S, N); //Очередная вершина
        if (tmp < 0 || tmp >= N) break;
        S[tmp] = 1;
        for (j = 0; j < N; j++)
        {
            if (S[j] == 1) continue;
            D[j] = (D[j] < D[tmp] + matrix[tmp * N + j]) ? D[j] : D[tmp] + matrix[tmp * N + j];
        }
    }

    for (i = 0; i < N; i++)
    {
        printf("Shortest route from %d to %d is %d\n", nu + 1, i + 1, D[i]);
    }
    free(S);
    free(D);

    //Алгоритм Прима
    //Делаем граф неориентированным
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            tmp = matrix[i * N + j];
            if (tmp == 10000) tmp = 0;
            if (tmp < matrix[j * N + i] && matrix[j * N + i] != 10000) tmp = matrix[j * N + i];
            matrix[i * N + j] = tmp;
            matrix[j * N + i] = tmp;
        }
    }

    printf("\nGraph's adjacency matrix: \n");
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            printf("%d\t", matrix[i * N + j]);
        }
        printf("\n");
    }

    printf("Enter target vertex: ");
    scanf("%d", &nu);

    int *U = calloc(N, sizeof(int));
    int *result = (int *)calloc(N * N, sizeof(int));
    int min = 10000, start_index = -1, end_index = -1;
    U[nu-1] = 1; //Выбираем вершину nu

    for(tmp = 0; tmp < N; tmp++)
    {
        for (i = 0; i < N; i++)
        {
            if (U[i] == 1)
            {
                for (j = 0; j < N; j++)
                {
                    if (U[j] != 1 && matrix[i * N + j] != 0 && matrix[i * N + j] < min)
                    {
                        min = matrix[i * N + j];
                        start_index = i;
                        end_index = j;
                    }
                }
            }
        }
        if (start_index != -1 && end_index != -1)
        {
            result[start_index * N + end_index] = min;
            result[end_index * N + start_index] = min;
            U[end_index] = 1;
            min = 10000;
            start_index = -1;
            end_index = -1;
        }
    }

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            printf("%d\t", result[i * N + j]);
        }
        printf("\n");
    }
    free(matrix);
    free(U);
    free(result);

    return 0;
}

int find_min_positive(int *arr, int *S, int N) //Находит минимальный положительный элемент массива и возвращает его индекс
{
    int i;
    int result = -1;
    int min = INT_MAX;
    for (i = 0; i < N; i++)
    {
        if (arr[i] < 0 || S[i] == 1)
            continue;
        if (arr[i] < min)
        {
            min = arr[i];
            result = i;
        }
    }
    return result;
}