Lab4 beta

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define INF 10000

int find_min(int S[15], int D[15], int N);
void printWay(int *P, int v);

int main()
{
    int i, j, tmp;
    int N = 15; //Количество вершин
    int matrix[15][15] = //Матрица смежности
    { {INF, 15, INF, INF, INF, INF, INF, INF, 10, 50, INF, INF, INF, INF, INF},
    {INF, INF, 20, 10, 30, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, 40, INF, INF, INF, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, 60, INF, INF, INF, 50, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, 5, INF, INF, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, 10, INF, INF, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, 10, INF, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, INF, INF, 25, 5, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, 15, INF, INF, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 15, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, INF, INF, 45, INF, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 15, INF, INF, INF, INF},
    {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 35, INF, 30, INF},
    {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 40},
    {10, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF}};
    int nu, target;
    int S[15] = { 0 };
    int D[15] = { 0 };
    int P[15];

    for (i = 0; i < N; i++) //Заполнение массива предыдущих вершин
    {
        P[i] = -1;
    }

    //Вывод матрицы смежности
    for (i = 0; i < N; i++)
    {
        printf("\t%d", i + 1);
    }
    printf("\n");
    for (i = 0; i < N; i++)
    {
        printf("%d\t", i + 1);
        for (j = 0; j < N; j++)
        {
            tmp = (matrix[i][j] == INF) ? 0 : matrix[i][j];
            printf("%d\t", tmp);
        }
        printf("\n");
    }

    printf("Dijkstra's algorithm:\n");
    printf("Enter start vertex nu: ");
    scanf("%d", &nu);
    printf("Enter target vertex: ");
    scanf("%d", &target);

    S[nu - 1] = 1; //Включаем вершину nu в S

    for (i = 0; i < N; i++)
    {
        if (matrix[nu - 1][i] < INF)
        {
            P[i] = nu - 1;
        }
    }

    for (i = 0; i < N; i++) //Инициализируем D
    {
        if (i == nu - 1)
        {
            D[i] = 0;
            continue;
        }
        D[i] = matrix[nu - 1][i];
    }

    for (i = 0; i < N; i++)
    {
        tmp = find_min(S, D, N); //Очередная вершина
        if (tmp < 0) break;
        S[tmp] = 1;

        for (j = 0; j < N; j++)
        {
            if (S[j] == 1) continue;
            if (D[j] > D[tmp] + matrix[tmp][j])
            {
                D[j] = D[tmp] + matrix[tmp][j];
                P[j] = tmp;
            }
        }
    }


    printf("\nShortest route from %d to %d is %d\n", nu, target, D[target-1]);
    printf("Path: ");
    printWay(P, target - 1);

    printf("\n\nPrima's algorithm\n");

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

    //Вывод матрицы смежности
    for (i = 0; i < N; i++)
    {
        printf("\t%d", i + 1);
    }
    printf("\n");
    for (i = 0; i < N; i++)
    {
        printf("%d\t", i + 1);
        for (j = 0; j < N; j++)
        {
            tmp = (matrix[i][j] == INF) ? 0 : matrix[i][j];
            printf("%d\t", tmp);
        }
        printf("\n");
    }

    int U[15] = { 0 };
    int result[15][15] = { 0 };
    int min = INF, start_index = -1, end_index = -1;
    int k;

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

    U[nu - 1] = 1; //Выбираем вершину nu

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

        if (start_index != -1 && end_index != -1)
        {
            result[start_index][end_index] = min;
            result[end_index][start_index] = min;
            U[end_index] = 1;
            min = INF;
            start_index = -1;
            end_index = -1;
        }
    }

    printf("Tree:\n");
    for (i = 0; i < N; i++)
    {
        printf("\t%d", i + 1);
    }
    printf("\n");
    for (i = 0; i < N; i++)
    {
        printf("%d\t", i + 1);
        for (j = 0; j < N; j++)
        {
            tmp = (result[i][j] == INF) ? 0 : result[i][j];
            printf("%d\t", tmp);
        }
        printf("\n");
    }
    return 0;
}

int find_min(int S[15], int D[15], int N)
{
    int result = -1;
    int min = INF;
    int i;

    for (i = 0; i < N; i++)
    {
        if (S[i] == 1) continue;
        if (D[i] < min)
        {
            min = D[i];
            result = i;
        }
    }

    return result;
}

void printWay(int *P, int v)
{
    if (v == -1)
    {
        return;
    }
    printWay(P, P[v]);
    printf("%d; ", (v + 1));
}