Enviado em 05/03/2017 - 15:32h
Criei a funçãovoid dijkstra(double **matrix, int origem, int destino, int linhas, int colunas);para obter o menor caminho como também o menor custo, mas não obtive sucesso.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void dijkstra(double **matrix, int origem, int destino, int linhas, int colunas);
void inicializa1(double **m, double v, int linha, int coluna);
void conecta1(double **m, int a, int b, double v);
void exibe_caminho1(double **m, int a, int b);
double** alocarMatriz(int Linhas, int Colunas);
void imprime_mat1(double **m, int linhas, int colunas);
int main(){
int g[tam][tam], g1[tam][tam], c[tam][tam], p[tam][tam], cd[tam][tam], a, b, resp, x, linhas=2, colunas, linha, coluna;
double **mat;
system("cls");
do{
printf("Digite o numero de colunas: ");
scanf("%d", &colunas);
} while (colunas < 1);
mat = alocarMatriz(linhas, colunas);
inicializa1(mat, 0,linhas,colunas);
do{
do{
printf("Digite o numero da linha: ");
scanf("%d", &linha);
} while (linha >= linhas);
do{
printf("Digite o numero da coluna: ");
scanf("%d", &coluna);
} while (coluna >= colunas);
if (linha != -1 && coluna != -1){
if (linha == coluna){
conecta1(mat, linha, coluna, sqrt(2.0));
}
else{
conecta1(mat, linha, coluna, 1.0);
}
}
imprime_mat1(mat, linhas, colunas);
} while (linha != -1 && coluna != -1);
do
{
printf("Digite o vertice de origem: ");
scanf("%d", &a);
if ((a < 0) || (a>linhas))
printf("\n\nVERTICE INVALIDO! DIGITE NOVAMENTE!\n\n");
}while ((a < 0) || (a > linhas));
do
{
printf("Digite o vertice de destino: ");
scanf("%d", &b);
if (b < 0 || a > colunas)
printf("\n\nVERTICE INVALIDO! DIGITE NOVAMENTE!\n\n");
}while ((colunas < 0) || (coluna> colunas));
printf("%d => ", a);
dijkstra(mat, a, b,linhas,colunas);
printf("%d", b);
system("PAUSE");
return 0;
}
void dijkstra(double **matrix, int origem, int destino, int linhas, int colunas){
int i,v, cont = 0,j;
double **ant, **tmp;
double **z; /* vertices para os quais se conhece o caminho minimo */
double min;
double **dist = (double **) malloc(linhas * sizeof(double*)); /* vetor com os custos dos caminhos */
/* aloca as linhas da matriz */
ant = (double **) malloc (linhas * sizeof(double *));
tmp = (double **) malloc (linhas * sizeof(double *));
if (ant == NULL) {
printf ("** Erro: Memoria Insuficiente **");
exit(-1);
}
z = (double **) malloc (linhas * sizeof(double *));
if (z == NULL) {
printf ("** Erro: Memoria Insuficiente **");
exit(-1);
}
for (i = 0; i < linhas; i++){
ant[i] = (double*)malloc(colunas * sizeof(double));
tmp[i] = (double*)malloc(colunas * sizeof(double));
z[i] = (double*)malloc(colunas * sizeof(double));
dist[i] = (double*)malloc(colunas * sizeof(double));
}
for (i = 0; i < linhas; i++) {
for(j=0;j<colunas; j++){
if (matrix[(origem - 1) * linhas + i][(origem - 1) * colunas + i] !=- {
ant[i][j] = origem - 1;
dist[i][j] = matrix[(origem-1)*linhas+i][(origem-1)*colunas+j];
}
else {
ant[i][j]= -1;
dist[i][j] = HUGE_VAL;
}
z[i][j]=0;
}
}
z[origem-1][destino-1] = 1.0;
dist[origem-1][destino-1] = 0.0;
/* Laco principal */
do {
/* Encontrando o vertice que deve entrar em z */
min = HUGE_VAL;
for (i=0;i<linhas;i++){
for(j=0;j<colunas;j++){
if (!z[i][j])
if (dist[i][j]>=0 && dist[i][j]<min) {
min=dist[i][j];v=i;
}
}
}
/* Calculando as distancias dos novos vizinhos de z */
if (min != HUGE_VAL && v != destino - 1) {
z[v][v] = 1;
for (i = 0; i < linhas; i++){
for(j=0; j<colunas; j++){
if (!z[i]) {
if ((matrix[v*linhas+i][v*colunas+j] != -1) && (dist[v][v] + matrix[v*linhas+i][v*colunas+j] < dist[i][j])) {
dist[i][j] = dist[v][v] + matrix[v*linhas+i][v*colunas+j];
ant[i][j] =v;
}
}
}
}
}
} while (v != destino - 1 && min != HUGE_VAL);
/* Mostra o Resultado da busca */
printf("\tDe %d para %d: \t", origem, destino);
if (min == HUGE_VAL) {
printf("Nao Existe\n");
printf("\tCusto: \t- \n");
}
else {
i = destino;
i = ant[i-1][i-1];
while (i != -1) {
// printf("<-%d",i+1);
tmp[cont][cont] = i+1;
cont++;
i = ant[i][i];
}
for (i = cont; i > 0 ; i--) {
printf("%d -> ", tmp[i-1]);
}
printf("%d", destino);
printf("\n\tCusto: %d\n",(int) dist[destino-1]);
}
}
void exibe_caminho1(double **m, int a, int b){
double k, d, r;
k = ((m[a][b]));
if (k != 0)
{
exibe_caminho1(m, a, k);
printf("%d => ", k);
exibe_caminho1(m, k, b);
}
}
double** alocarMatriz(int Linhas, int Colunas){
int i, j;
double **m = (double**)malloc(Linhas * sizeof(double*));
for (i = 0; i < Linhas; i++){
m[i] = (double*)malloc(Colunas * sizeof(double));
for (j = 0; j < Colunas; j++){
m[i][j] = 0;
}
}
return m;
}
void inicializa1(double **m, double v, int linha, int coluna){
int i, j;
i = j = 0;
while (i != linha)
{
while (j != coluna)
{
m[i][j] = v;
j++;
}
j = 0;
i++;
}
}
void conecta1(double **m, int a, int b, double v){
m[a][b] = v;
}
void imprime_mat1(double **m, int linhas, int colunas){
int i, j, k;
for (i = 0; i < linhas; i++){
for (j = 0; j < colunas; j++){
printf("%.1f ", m[i][j]);
}
printf("\n");
}
system("PAUSE");
}
Customizar a Instalação do Linux Debian com Preseed
Atualizando o Passado: Linux no Lenovo G460 em 2025
aaPanel - Um Painel de Hospedagem Gratuito e Poderoso
Um modo leve de ouvir/ver áudio/vídeo da internet em máquinas pererecas
Resolver algumas mensagens de erro do SSH
Instalar módulo de segurança do Banco do Brasil Warsaw do tipo .run
Sem espaço na partição home (4)
Aprendendo mais sobre Linux com livro (6)
Procrastinação e autossabotagem são problemas muito comuns na sociedad... (6)