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");
}
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Como abrir o pycharm no linux (2)
VMs e Interfaces de Rede desapareceram (12)