Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

AJBM

Grafos

Recommended Posts

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).

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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é!

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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();
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.