Ir para o conteúdo
AJBM

Grafos

Mensagens Recomendadas

AJBM

Boas!

Eu tenho dois grafos em que num tenho as distancia e noutro tenho o tempo, eu queria saber se é possível juntar estes dois grafos, isto é, quero o caminho mais curto (distancia menor e tempo menor).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Ja reparaste que esse problema (distancia menor e tempo menor) pode nao ter solucao?


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

a única maneira seria verificar o conjunto de soluções de um e o conjunto de soluções de outro e verificar se existe sobreposição de algum resultado.

isto porque como foi dito, podes não ter solução


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
AJBM

Pois...

Eu para um critério já fiz, o pior é quando envolve mais de que um critério.

Eu pensei noutra solução foi criar um Tipo Peso que tivesse distancia e o tempo, e assim tinha tudo no mesmo grafo...

Será que assim é mais simples ou é a mesma coisa??

Em todo caso vou tentar o que disseste HappyHippyHippo

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
jsWizard

se os nodos do grafo são os mesmos, então não vejo razão para teres dois grafos, podes simplesmente ter duas propriedades nas conecções do nodos.. uma propriedade representa a distância e outra o tempo. Podes depois fazer a pesquisa pelo melhor caminho em termos de distância ou de tempo, que eventualmente podem ser caminhos diferentes.

Inté!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

se os nodos do grafo são os mesmos, então não vejo razão para teres dois grafos, podes simplesmente ter duas propriedades nas conecções do nodos.. uma propriedade representa a distância e outra o tempo. Podes depois fazer a pesquisa pelo melhor caminho em termos de distância ou de tempo, que eventualmente podem ser caminhos diferentes.

Inté!

o que foi dito era que tinha dois grafos, nunca foi dito que os tinha descrito em estruturas de dados diferentes e/ou localização de memória diferentes.

dizer que tem dois grafos não implica directamente a suposição anterior.

nada impede de ter em memória a descrição de todos os nós de um grafo, e ter milhentas descrições de subgrafos provenientes do supragrafo (mesmo sem alguns nós do grafo original).


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
AJBM

Boas!

Eu já calculei o caminho mais curto, mas agora tenho de calcular o caminho mais longo.

Alguém pode dar uma dica

/**
 * Devolve um iterador com os índices dos vértices que estão no caminho mais
 * curto entre os dois vértices especificados.
 * Lança uma Execao se a Network estiver vazia.
 *
 * @param startIndex o índice inicial
 * @param targetIndex o índice alvo
 * @param tipo indica se queremos o caminho com peso menor ou maior
 * @return um iterador com os índices dos vértices que estão no caminho mais
 * curto entre os dois vértices especificados
 * @throws Execoes se a Network estiver vazia
 */
@Override
protected Iterator<Integer> iteratorShortestPathIndices(int startIndex, int targetIndex, int tipo) throws Execoes {
 int index;
 double weight;
 int conta = 0;
 int[] predecessor = new int[numVertices];
 Heap<Double> traversalMinHeap = new Heap<Double>();
 ArrayUnorderedList<Integer> resultList =
		 new ArrayUnorderedList<Integer>();
 LinkedStack<Integer> stack = new LinkedStack<Integer>();
 int[] pathIndex = new int[numVertices];
 double[] pathWeight = new double[numVertices];
 for (int i = 0; i < numVertices; i++) {
	 pathWeight[i] = Double.POSITIVE_INFINITY;
 }
 boolean[] visited = new boolean[numVertices];
 for (int i = 0; i < numVertices; i++) {
	 visited[i] = false;
 }
 if (!indexIsValid(startIndex) || !indexIsValid(targetIndex)
		 || (startIndex == targetIndex) || isEmpty()) {
	 return resultList.iterator();
 }
 pathWeight[startIndex] = 0;
 predecessor[startIndex] = -1;
 visited[startIndex] = true;
 weight = 0;
 for (int i = 0; i < numVertices; i++) {
	 if (!visited[i]) {
		 pathWeight[i] = pathWeight[startIndex] + adjMatrix[startIndex][i];
		 predecessor[i] = startIndex;
		 traversalMinHeap.addElement(new Double(pathWeight[i]));
	 }
 }
 do {
	 weight = (traversalMinHeap.removeMin()).doubleValue();
	 traversalMinHeap.removeAllElements();
	 if (weight == Double.POSITIVE_INFINITY) // no possible path
	 {
		 return resultList.iterator();
	 } else {
		 index = getIndexOfAdjVertexWithWeightOf(visited, pathWeight, weight);
		 visited[index] = true;
	 }
	 for (int i = 0; i < numVertices; i++) {
		 if (!visited[i]) {
			 if (tipo == 1) {//devolve o caminho mais curto
				 if ((adjMatrix[index][i] < Double.POSITIVE_INFINITY)
						 && (pathWeight[index] + adjMatrix[index][i]) < pathWeight[i]) {
					 pathWeight[i] = pathWeight[index] + adjMatrix[index][i];
					 predecessor[i] = index;
				 }
			 } else {//devolve o caminho mais longo
				 if ((adjMatrix[index][i]< Double.POSITIVE_INFINITY)
		 && ((pathWeight[index]+adjMatrix[index][i]) > pathWeight[i])) {

					 System.out.println(pathWeight[index] + " - - - " + adjMatrix[index][i]);
					 pathWeight[i] = pathWeight[i]+adjMatrix[index][i];
					 predecessor[i] = index;
				 }
			 }
			 traversalMinHeap.addElement(new Double(pathWeight[i]));
		 }
	 }
 } while (!traversalMinHeap.isEmpty() && !visited[targetIndex]);
 index = targetIndex;
 stack.push(new Integer(index));
 do {
	 index = predecessor[index];
	 stack.push(new Integer(index));
 } while (index != startIndex);
 while (!stack.isEmpty()) {
	 resultList.addToRear((stack.pop()));
 }
 return resultList.iterator();
}

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.