Ajuda - Dijkstra [RESOLVIDO]

Pirotas
(usa Outra)

Enviado em 13/11/2009 - 16:59h

Oi pessoal, entrei na onda da linguagem C este semestre e tenho andado aflito com aquilo!!!
Tenho um trabalho para entregar na próxima 4ª dia 18 e nem sei como pegar. Ora aqui vai:

Tenho de encontrar o caminho mais curto numa rede grafo.

O código deve ser construído de modo a obter os dados através da leitura do teclado (na realidade vão ser lidos de um ficheiro mas a indicação é construir como se fossem lidos do teclado). Os ficheiros a ler têm a seguinte estrutura:

1ª linha
vértice de origem espaço vértice de destino
2ª linha
número de vértices
3ª linha
número de arestas
4ª e seguintes
vértice inicial espaço vértice final espaço custo

Segue o grafo de exemplo:

0 4
6
11
0 1 3
1 0 9
1 5 1
1 3 7
2 5 9
3 4 9
4 0 3
4 3 8
5 3 5
5 2 6
5 1 6

O output deve ser:
custo = <custo do caminho>
Vértices do caminho especificando a sequência.

Para o exemplo dado seria:

custo=18
0 1 5 3 4

A definição do grafo assenta nas seguintes premissas:
1. o grafo é dirigido, pelo que o custo de u&#8594;v é diferente de v&#8594;u.
2. o grafo tem uma dimensão máxima de 100 vértices e 300 arestas.
3. cada vértice está ligado no máximo a outros três vértices.

Eu não queria que me fizessem o trabalho mas se não for assim acho que levo ZERO. :-) Já tentei adaptar o código do Vanderson mas estou completamente bloqueado.

Agradeço já qualquer tentativa, frutuosa ou não, para me ajudar!

saitam
(usa Slackware)

Enviado em 16/11/2009 - 10:59h

dê uma olhada neste código fonte http://mundodacomputacao.home.sapo.pt/CaminhoMinimo.zip, é do algoritmo do menor caminho Dijkstra, esse foi um trabalho de Teoria dos Grafos da Faculdade, e resolvi publicar na página, para quem precisar.

PS: Se for usar parte do código não esquecer de citar a fonte do mesmo.

Pirotas
(usa Outra)

Enviado em 16/11/2009 - 18:29h

Não poderei usar o seu código nem citá-lo uma vez que isso me daria automaticamente nota ZERO :-)
Vou tentar construir com a ajuda do seu relatório, pode ser que resulte.
Obrigado

ramontcruz
(usa Ubuntu)

Enviado em 16/11/2009 - 18:53h

a tecnica é velha. mas depois disso o dijkstra ficou mais facil pra mim :-)

Pirotas
(usa Outra)

Enviado em 17/11/2009 - 19:02h

Vou fazer uma pergunta básica mas tem de ser:

O que é um teste de mesa?

saitam
(usa Slackware)

Enviado em 18/11/2009 - 10:12h

teste de mesa, você faz a depuração do programa de uma linguagem de programação qualquer, mas sem auxílio do compilador, inclusive faz o papel do processador e do compilador no braço mesmo.
Como fazer?
Pegue uma folha de papel em branco e anote o resultado de cada linha do código fonte ou do pseudocódigo e compare com o resultado obtido com a execução do programa no computador.

PS: Antes disso é necessário entender o código fonte ou pseudocódigo para saber qual seria o resultado esperado para conferir com o teste de mesa.

Veja nesse site: http://www.brasilacademico.com/ed/testemesa.htm

Pirotas
(usa Outra)

Enviado em 18/11/2009 - 13:05h

Era o que eu pensava.... neste código é um pouco puxado mas se tiver que ser......

Pirotas
(usa Outra)

Enviado em 19/11/2009 - 17:09h

Foi assim que acabei por entregar o trabalho (atenção que para grafos com mais de 100 arestas é necessário alterar a dimensão da matriz e da tabela) (poderá dar erro pois só passou em 15 testes de 18, não há nada perfeito!!!)

Ainda podem ver como passar matrizes bidimensionais por valor, é só olhar o código.

main
[code]
#include "proj1.h"

int main(int argc, char** argv){

int nvertices, narestas, origem, destino;
int matriz[100][3];
int tab[4][110];
int k = 0;

scanf("%d %d", &origem, &destino);
scanf("%d", &nvertices);
scanf("%d", &narestas);

/*organizar a matriz do grafo*/
do{
scanf("%d %d %d", &(matriz[k][0]), &(matriz[k][1]), &(matriz[k][2]));
k++;
}while(k < narestas);

/*organizar a tabela auxiliar*/
k = 0;
for(k = 0; k < narestas; k++){
tab[0][k] = k;/*vertice, indice*/
tab[1][k] = INF;/*custo, indice*/
tab[2][k] = 0;/*bloqueado(0 não/ 1 sim), indice*/
tab[3][k] = 0;/*vertice anterior, indice*/
}

tab[1][origem] = 0;/*origem a zero*/

/*define os parametros de inicio da busca*/
tab[1][origem] = 0;/*define o custo inicial a zero*/
tab[3][origem] = 0;/*o precedente da origem é a origem*/

dijkstra(matriz, destino, origem, nvertices, narestas, tab);

return 0;
}[\code]

proj1.c
[code]
#include "proj1.h"

void dijkstra(int matriz[100][3], int destino, int origem, int nvertices, int narestas, int tab[4][110])
{
int i, j;
int t, p;
int caminho[100];
int prox = 0, min = INF, destino_aresta = 0;

for(t = 0; t < nvertices ; t++){
min=INF;
for(i = 0; i < nvertices; i++){
if((tab[1][i] < min) && (tab[2][i] == 0)){
prox = tab[0][i];/*próximo nó, precedência da origem é a origem*/
min = tab[1][i];/*novo mínimo*/
}
}

tab[2][prox]=1;/*bloquear vértices (linha2)*/
j=0;
while(j < narestas){
if(matriz[j][0] == prox){
destino_aresta = matriz[j][1];
if(min + matriz[j][2] < tab[1][destino_aresta]){/*compara o novo mínimo com o valor da tabela*/
tab[1][destino_aresta] = min + matriz[j][2];/*actualiza o custo até ao momento*/
tab[3][destino_aresta] = prox;/*define qual o vertice anterior*/
}
}
j++;
}
}

printf("custo=%d\n", tab[1][destino]);

/*obter o caminho através da linha dos vertices anteriores da tabela auxiliar*/
i = 0;
p = destino;
while(p != origem){
caminho[i] = p;
i++;
p = tab[3][p];
}

printf("%d",origem);/*imprime a origem*/

/*imprime o resto do caminho*/
for(i--; i != -1; i--){
printf(" %d", caminho[i]);
}

printf("\n");
}
[\code]

proj1.h
[code]
#ifndef PROJ1_H_
#define PROJ1_H_

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define INF 999/*valor elevado, tratar como infinito*/

void dijkstra(int matriz[100][3], int destino, int origem, int nvertices, int narestas, int tab[4][110]);

#endif /* PROJ1_H_ */
[\code]

Pirotas
(usa Outra)

Enviado em 19/11/2009 - 17:11h

É claro que tive de fazer os tais testes de mesa.

Obrigado a todos pelas ajudas e dicas que disponibilizaram.

Desculpem por ter usado mal as notações de code

Pirotas
(usa Outra)

Enviado em 22/11/2009 - 19:40h

Julgo que já encontrei a solução final.

Sem ser necessário alocar espaço para a matriz e a tabela, sabendo qual o número de ligações, definindo no ficheiro *.h as constantes das dimensões resolve-se o problema.

Para o *.h:
definindo as constantes
#define MX 300/*numero de linhas da matriz*/
#define MY 3/*numero de colinas da matriz*/
#define TX 4/*numero de linhas da tabela*/
#define TY 300/*numero de colunas da tabela*/
a função
void dijkstra(int matriz[MX][MY], int destino, int origem, int nvertices, int narestas, int tab[TX][TY]);

Para o *.c:
a função
void dijkstra(int matriz[MX][MY], int destino, int origem, int nvertices, int narestas, int tab[TX][TY])

Sabendo o número de ligações, as constantes a alterar são a MX e a TY