Considere que a matriz D(nxn) armazena as distâncias entre n cidades. Considere que D[i][j] pode ser diferente de D[j][i]. A alocação de memória para D deve ser feita dinamicamente, uma vez conhecido o valor de n. Gerar a matriz com valores aleatórios no intervalo [1, 99] e escrever uma função int caminho(int ** D, int n, int x, int y, int *c1, int * c ) que calcula o menor caminho entre a cidade x e a cidade y , passando pelas cidades c1 e c2. A função deve retornar a distância total deste caminho e quais são as cidades intermediárias c1 e c2. Escrever a função main() para testar o programa.

Passo 1

O enunciado pede um programa em C que, dada uma matriz D (n×n) com distâncias entre cidades (possivelmente assimétrica), encontre o menor caminho de uma cidade x até y, passando exatamente por duas cidades intermediárias c1 e c2. Vamos usar alocação dinâmica, geração de números aleatórios e uma busca exaustiva para escolher c1 e c2.

Passo 2

Alocar dinamicamente a matriz D de tamanho n×n usando malloc. Em C, criamos um vetor de ponteiros int** D = malloc(n * sizeof(int*)); e para cada linha D[i] = malloc(n * sizeof(int));

Passo 3

Preencher a matriz D com valores rand()%99 + 1 (no intervalo [1,99]) para i ≠ j, e colocar D[i][i] = 0 para facilitar a leitura. Inicializar a semente com srand(time(NULL)).

Passo 4

Implementar a função int caminho(int **D, int n, int x, int y, int *c1, int *c2) usando dois loops aninhados que percorrem todos os pares (i,j) distintos de x e y. Para cada par, calcular soma = D[x][i] + D[i][j] + D[j][y], acompanhar o mínimo e atualizar *c1 e *c2.

Passo 5

Escrever a função main(): ler n, x e y do usuário; alocar e preencher D; imprimir a matriz; chamar caminho(D,n,x,y,&c1,&c2); exibir o percurso e a distância total; por fim, liberar toda a memória alocada.

Resposta

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
int caminho(int **D, int n, int x, int y, int *c1, int *c2) {
int melhor = INT_MAX;
for (int i = 0; i < n; i++) {
if (i == x || i == y) continue;
for (int j = 0; j < n; j++) {
if (j == x || j == y || j == i) continue;
int soma = D[x][i] + D[i][j] + D[j][y];
if (soma < melhor) {
melhor = soma;
*c1 = i;
*c2 = j;
}
}
}
return melhor;
}
int main() {
int n, x, y, c1, c2;
srand(time(NULL));
printf("Número de cidades: ");
scanf("%d", &n);
printf("Cidade de origem (0-%d): ", n-1);
scanf("%d", &x);
printf("Cidade de destino (0-%d): ", n-1);
scanf("%d", &y);

int **D = malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
    D[i] = malloc(n * sizeof(int));
    for (int j = 0; j < n; j++) {
        if (i == j)
            D[i][j] = 0;
        else
            D[i][j] = rand() % 99 + 1;
    }
}

printf("Matriz de distâncias:\n");
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%4d", D[i][j]);
    }
    printf("\n");
}

int dist = caminho(D, n, x, y, &c1, &c2);
printf("\nMelhor caminho: %d -> %d -> %d -> %d\n", x, c1, c2, y);
printf("Distância total: %d\n", dist);

for (int i = 0; i < n; i++) free(D[i]);
free(D);
return 0;
}

Exercícios relacionados