Ir para o conteúdo
scorpionmad

GRAFOS ALGORITMO

Mensagens Recomendadas

scorpionmad

bons dias,

É o seguinte, recebi agr o meu trabalho final de programação que corresponde à construção de um algoritmo que permite ao programa calcular um percurso do local x a y (inseridos pelo utilizador). Para isso temos de criar um algoritmo utilizando a teoria de grafos. ja pesquisei em muitos locais na internet, muitos tutoriais mas nada que ajude, será que alguem me poderia ajudar? o meu maior problema é na construção da tabela. não percebo como o fazer e sem isso nao poderei continuar. Preciso de ajuda, é urgente, tenho de entregar o trabalho no inicio de janeiro.

Obrigado e cumprimentos.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
XicoXperto

o meu maior problema é na construção da tabela.

A tabela que falas é da distancia do ponto A->B?

Como é que tens a informacao de ponto a ponto?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Será que o que queres é o um algoritmo como o de dijkstra?

http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
scorpionmad

a informação ponto a ponto é o programa que lê de um ficheiro, a informação está guardada no formato:

Lisboa    Porto    350

Porto    Lisboa    350

Lisboa    Braga    400

Braga    Lisboa    400

Porto    Braga    170

Braga    Porto    170

em que o 1º nome e o local de origem da estrada, o 2º o local de destino e 3º o numero de km.

e o que o programa tem de fazer e calcular qual o percurso mais longo ou mais curto por exemplo de x a y (inseridas pelo utilizador e que existem no ficheiro que é fornecido ao programa)

o meu problema está na criação da matriz que guarda os percursos que existem. tentei-me basear na teoria de grafos mas nao compreendo como implementar a tabela. O Algoritmo de Dijkstra escolhe o caminho mais curto ou mais longo de um grafo, mas este ja e o passo seguinte, primeiro necessito a criação da tabela, e e nisto que quero ajuda se fosse possivel. Obrigado pela colaboração

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
XicoXperto

Vamos então ver o teu problema é passares do ficheiro para o programa, ou seja, como armazenar a informação, é isso né?

Sendo assim o que eu faria era criar uma  estrutura com essa informacao

typedef struct distancia{
          char localidade1[64];
          char localidade2[64];
          int valor;
  } distancia;

//então se fizeres:
distancia lista[200];//ficas com 200 blocos para pores informação (ou seja dá para 200 linhas do ficheiro.

Será que o que queres é o um algoritmo como o de dijkstra?

http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra

Agora como calcular o algoritmo de Dijkstra como disse o KTachyon resolvia esse problema

E para armazenar a informação dos calculos necessários de Dijkstra faria uma estrutura também, mas dá uma leitura ao algoritmo.

typedef struct distancia_necessaria{
          char localidade[64];
          char caminho_percorrido_ate_a_localidade[64];
          int total_distancia;
  } distancia_necessaria;

Entao para aplicar isto a minha seria (caminho de A->Z):

iteração 1:

1- buscar à lista de "distancia" a primeira que contenha uma localidade A

por exemplo na lista de distancias encontras uma com a seguinte info:

    localidade1= "D";

    localidade2= "A";

    valor=10;

   

2-então cria-se uma variavel do tipo" distancia_necessaria" com a info:

    localidade= "D";

    caminho_percorrido_ate_a_localidade= "A->D"; // isto é um exemplo, aqui interpretas como quiseres

    total_distancia= 10;

3- removes essa "distancia" da lista, para nao a calculares outra vez

4- e fazes isto para todas as "distancia" que contenham a localidade A

iteracao 2:

- apos isso, procuras nas "distancia_necessaria" a que tiver menor valor "total_distancia" e dai tiras a localidade, sendo assim vais repetir os passos 1,2,3 e 4  para todas as "distancia" que contiverem a essa localidade

iteracao final.

quando encontrares o Z é pq já é o caminho mais curto, logo pegas na "distancia_necessaria" e o "caminho_percorrido_ate_a_localidade" é o caminho mais curto.

Espero que isto ajude

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.