Lab 4

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

int main()
{
    unsigned int N, nu;
    unsigned int i, j, tmp;

    printf("Enter amount of vertexes: ");
    scanf("%d", &N);

    int *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;
        }
    }

    printf("Enter target vertex: ");
    scanf("%d", &tmp);
    nu = tmp - 1;

    unsigned 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) 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("D[%d] = %d\n", i + 1, D[i]);
    }
    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;
}