Considere que a matriz
armazena as distâncias entre n cidades. Considere que
pode ser diferente de
. 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 **
, int
, int
, int
, int *c1, int *
) 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>
#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 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));
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;
}