Roy Floyd

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

void afisare(int **mat, int n) {
    int i, j;

    printf("\nMatricea costurilor minime:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("d[%i][%i] = %i\t", i, j, mat[i][j]);
        printf("\n");
    }

}

void roy_floyd(int **w, int n, int **d, int MAX) {
    int i, j, k;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            d[i][j] = w[i][j];
    for (j = 0; j < n; j++)
        for (i = 0; i < n; i++)
            if (d[i][j] < MAX)
                for (k = 0; k < n; k++)
                    if (d[i][k] > d[i][j] + d[j][k])
                        d[i][k] = d[i][j] + d[j][k];
    afisare(d, n);
}

int **alocare(int m, int n) {
    int **mat, i;

    mat = (int **)malloc(m*sizeof(int *));
    for (i = 0; i < m; i++)
        *(mat + i) = (int *)malloc(n*sizeof(int));
    return mat;
}

void dezalocare(int **mat, int m) {
    int i;

    for (i = 0; i < m; i++)
        free(*(mat + i));
    free(mat);
}



void main() {
    int n, MAX = 9999, **w, **d, i, j, m, vf1, vf2, c;

    printf("Nr. varfuri: "); scanf_s("%i", &n);
    printf("Nr. muchii: "); scanf_s("%i", &m);

    w = alocare(n, n);
    d = alocare(n, n);

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (i == j)
                w[i][j] = 0;
            else
                w[i][j] = MAX;
    for (i = 0; i < m; i++) {
        printf("Varf initial: "); scanf_s("%i", &vf1);
        printf("Varf final: "); scanf_s("%i", &vf2);
        printf("Cost drum: "); scanf_s("%i", &c);

        w[vf1 - 1][vf2 - 1] = w[vf2 - 1][vf1 - 1] = c;
    }

    roy_floyd(w, n, d, MAX);
    dezalocare(w, n);
    dezalocare(d, n);

    _getch();
}