Caminho + longo!

E ai galera… tava navegando pela net e achei um exemplo de Dijkstra no site do Daniel Tritone http://stupid.blogsome.com/codes/ ele é bem bacaninha e completo…
Ai como pintou um trabalhinho da facul, pra fazer o “inverso” (Caminho + longo entre dois pontos) de Dijkstra resolvi mexer nos fontes e tentar aproveitar algo!..
No entanto estou apanhando bastante para fazer isso!..
-> os fontes originais estão aqui: http://www.esnips.com/doc/e5346e49-0149-4022-b105-bca43090b3cd/grafo

no meu projeto aqui eu alterei a arquivo Caminho.java, mais especificamente no método: public No[] menorCaminho(No origem, No destino)

para isso aqui:

public No[] menorCaminho(No origem, No destino) {
		int i = 0, j = 0;
		No maior = null, atual = null; // Último nó adicionado a N
		
		// Inicialização
		N = new No[nos.length];
		N[j++] = origem;
		
		for (i = 0; i < nos.length; i++) {
			nos[i].setD(ZERO);
			nos[i].setAnterior(null);
		}
		
		atual = origem;
		
		// Distância de um nó para ele mesmo é inexistente
		atual.setD(0); 
		
		No[] vizinhos = atual.getVizinhos();
		
		if (vizinhos == null)
			return null;
		
		for (i = 0; i < vizinhos.length; i++)
			vizinhos[i].setAnterior(atual);
		
		while (atual.compareTo(destino) != 0) {
			maior = null;
			
			for (i = 0; i < nos.length; i++) {
				if (!emN(nos[i])) {
					if (maior == null)
						maior = nos[i];
					
					if (atual.getD() - atual.getPeso(nos[i]) > nos[i].getD()) {
						if (atual.getPeso(nos[i]) > ZERO) {
							nos[i].setD(atual.getD() - atual.getPeso(nos[i]));
							
							if (atual.getPeso(nos[i]) > ZERO)
								nos[i].setAnterior(atual);
						}
					}
					
					if (nos[i].getD() > maior.getD()) {
						maior = nos[i];
					}
				}
			}
			
			atual = maior;
			N[j++] = atual;
		}
		
		Stack pilha = new Stack();
		No[] retorno = new No[N.length];
		atual = N[j - 1];
		i = 0;
		
		while (atual != null) {
			pilha.push(atual);
			atual = atual.getAnterior();
		}
		
		j = pilha.size();
		for (i = 0; i < j; i++)
			retorno[i] = (No)pilha.pop();
		
		return retorno;
	}

So que não deu muito certo… será que alguém pode me dar uma mão?!..
Não estou bem certo… mas acho que tenho que mexer em algo na classe No.java, so que não enxerguei aqui ainda!

qq ajuda é bem vinda!!

desisti de mexer nesse programa…
muito complexo… hehehehehehe… sempre dava erro quando eu mudava algo… ai resolvi navegar um pokinho + na net e achei este outro exemplo do algortimo de Dijkstra:

import java.util.*;
public class Dijkstra {
    
    //define some constants
    public static final int INF=Integer.MAX_VALUE; //infinity
    public static final int NUM_VERTICES=8;
    
    //now define the cities
    public static final int HNL=0;
    public static final int SFO=1;
    public static final int LAX=2;
    public static final int ORG=3;
    public static final int DFW=4;
    public static final int LGA=5;
    public static final int PVD=6;
    public static final int MIA=7;
    public static final int nonexistent=8;
        
    //start and end vertices
    public static final int FIRST_VERTEX=HNL;
    public static final int LAST_VERTEX=MIA;
    
    //list of names of cities, for output
    private String[] name={"HNL","SFO","LAX","ORD","DFW","LGA","PVD","MIA"};
    
    //now the initial distance matrix ("weight")
    private int weight[][]=
    {
      /* HNL    SFO     LAX     ORD     DFW     LGA     PVD     MIA */
        {0,     INF,    2555,   INF,    INF,    INF,    INF,    INF }, //HNL
        {INF,   0,      337,    1843,   INF,    INF,    INF,    INF }, //SFO
        {2555,  337,    0,      1743,   1233,   INF,    INF,    INF }, //LAX
        {INF,   1843,   1742,   0,      802,    INF,    849,    INF }, //ORD
        {INF,   INF,    1233,   802,    0,      1387,   INF,    1120}, //DFW
        {INF,   INF,    INF,    INF,    1387,   0,      142,    1099}, //LGA
        {INF,   INF,    INF,    849,    INF,    142,    0,      1205}, //PVD
        {INF,   INF,    INF,    INF,    1120,   1099,   1205,   0   }, //MIA
    };
    
    /*** Dijkstra's Algorithm starts here ***/
    int[] distance=new int[NUM_VERTICES];
    boolean[] tight=new boolean[NUM_VERTICES];
    int[] predecessor=new int[NUM_VERTICES];
    
    private int minimalNontight(){
        int j,u;
        
        for(j=FIRST_VERTEX; j<LAST_VERTEX; j++){
            if(!tight[j])
                break;
        }
        
        assert(j<=LAST_VERTEX);
        
        u=j; /* u is now the first vertex with nontight estimate, but maybe not the minimal one. */
        for(j++; j<=LAST_VERTEX; j++)
            if(!tight[j] && distance[j]<distance[u])
                u=j;
        
        return u;
    }
    
    private boolean successor(int u, int z){
        return ((weight[u][z]!=INF) && u!=z);
    }
    
    //now initialise these arrays
    public void dijkstra(int s){
        int z,u;
        int i;
        
        distance[s]=0;
        for(z=FIRST_VERTEX; z<=LAST_VERTEX; z++){
            if(z!=s) distance[z]=INF;
            
            tight[z]=false;
            predecessor[z]=nonexistent;
        }
        
        for(i=0; i<NUM_VERTICES; i++){
            u=minimalNontight();
            tight[u]=true;
            
            if(distance[u]==INF)
                continue;
            
            for(z=FIRST_VERTEX; z<=LAST_VERTEX; z++)
                if(successor(u,z) && !tight[z] && (distance[u]+weight[u][z]<distance[z])){
                    distance[z]=distance[u]+weight[u][z]; //we've found a shortcut
                    predecessor[z]=u;
                }
        }      
    }
    
    public void printShortestPath(int origin, int destination){
        
        assert(origin!=nonexistent && destination!=nonexistent);
        dijkstra(origin);
        
        System.out.println("The shortest path from "+name[origin]+" to "+name[destination]+" is:\n");
        
        Stack<Integer> st=new Stack<Integer>();

        for(int v=destination; v!=origin; v=predecessor[v])
            if(v==nonexistent){
                System.out.println("non-existent (because the graph is not connected).");
                return;
            }else{
                st.push(v);
            }
        
        st.push(origin);
        
        while(!st.empty())
            System.out.print(name[st.pop()]+" -> ");
        
        System.out.println("[finished]");
    }
    
    public Dijkstra(){ return; }
    
    public static void main(String[] unused){
        new Dijkstra().printShortestPath(LAX, MIA);
    }
  
}

Mais facil de entender, funções mais simples, a entrada da matriz é feita no proprio algoritmo…
BACANINHA… resolve o problema de menor caminho perfeitamente!..
ai resolvi mexer nele, para tentar fazer com que ele calculasse o “maior caminho” ou “caminho + longo” ou “caminho com maior profundidade”…
e alterei ele para seguinte maneira:

import java.util.*;
public class Dijkstra {
    
    //define some constants
    public static final int INF=Integer.MIN_VALUE; //infinity
    public static final int NUM_VERTICES=8;
    
    //now define the cities
    public static final int v1=0;
    public static final int v2=1;
    public static final int v3=2;
    public static final int v4=3;
    public static final int v5=4;
    public static final int v6=5;

    public static final int nonexistent=6;
        
    //start and end vertices
    public static final int FIRST_VERTEX=v1;
    public static final int LAST_VERTEX=v6;
    
    //list of names of cities, for output
    private String[] name={"v1","v2","v3","v4","v5","v6"};
    
    //now the initial distance matrix ("weight")
    private int weight[][]=
    {
      /* v1		v2		v3		v4		v5		v6    */
        {0,     2,    	10,		INF,    INF,    INF }, //v1
        {2,		0,      INF,    2,      INF,    INF }, //v2
        {10,  	INF,    0,      INF,    10,     INF }, //v3
        {INF,   2,  	INF,   	0,      50,     INF }, //v4
        {INF,   INF,    10,  	50,     0,      5	}, //v5
        {INF,   INF,    INF,    INF,    5,		0   }, //v6
   
    };
    
    /*** Dijkstra's Algorithm starts here ***/
    int[] distance=new int[NUM_VERTICES];
    boolean[] tight=new boolean[NUM_VERTICES];
    int[] predecessor=new int[NUM_VERTICES];
    
    private int minimalNontight(){
        int j,u;
        
        for(j=FIRST_VERTEX; j<LAST_VERTEX; j++){
            if(!tight[j])
                break;
        }
        
        assert(j<=LAST_VERTEX);
        
        u=j; /* u is now the first vertex with nontight estimate, but maybe not the minimal one. */
        for(j++; j<=LAST_VERTEX; j++)
            //if(!tight[j] && distance[j]<distance[u])
        	if(!tight[j] && distance[j]>distance[u])
                u=j;
        
        return u;
    }
    
    private boolean successor(int u, int z){
        return ((weight[u][z]!=INF) && u!=z);
    }
    
    //now initialise these arrays
    public void dijkstra(int s){
        int z,u;
        int i;
        
        distance[s]=0;
        for(z=FIRST_VERTEX; z<=LAST_VERTEX; z++){
            if(z!=s) distance[z]=INF;
            
            tight[z]=false;
            predecessor[z]=nonexistent;
        }
        
        for(i=0; i<NUM_VERTICES; i++){
            u=minimalNontight();
            tight[u]=true;
            
            if(distance[u]==INF)
                continue;
            
            for(z=FIRST_VERTEX; z<=LAST_VERTEX; z++)
            	//if(successor(u,z) && !tight[z] && (distance[u]+weight[u][z]<distance[z])){
                if(successor(u,z) && !tight[z] && (distance[u]+weight[u][z]>distance[z])){
                    distance[z]=distance[u]+weight[u][z]; //we've found a shortcut
                    predecessor[z]=u;
                }
        }      
    }
    
    public void printShortestPath(int origin, int destination){
        
        assert(origin!=nonexistent && destination!=nonexistent);
        dijkstra(origin);
        
        System.out.println("The shortest path from "+name[origin]+" to "+name[destination]+" is:\n");
        
        Stack<Integer> st=new Stack<Integer>();

        for(int v=destination; v!=origin; v=predecessor[v])
            if(v==nonexistent){
                System.out.println("non-existent (because the graph is not connected).");
                return;
            }else{
                st.push(v);
            }
        
        st.push(origin);
        
        while(!st.empty())
            System.out.print(name[st.pop()]+" -> ");
        
        System.out.println("[finished]");
    }
    
    public Dijkstra(){ return; }
    
    public static void main(String[] unused){
        new Dijkstra().printShortestPath(v1, v6);
    }
  
}

Entretanto, eu descobri que o algoritmo so faz o caminho + longo se este caminho estiver explicito do 1° nó pra frente…
Por exemplo:

v1—v2 valendo 5
v1—v3 valendo 10

ele escolhe v1—v3…
mas se o caminho de v3 até o nó final for “menor”… ele me retornará esse caminho pq, no primeiro teste ele definiu que v1 pra v3 é melhor (que é verdade), mas não levou em conta o resto da rede…

Se existisse v2—v4 valendo 1000
e v3----v4 valendo 5… o caminho final retornado seria v1—v3—v4 com a soma final igual a 15 sendo que o outro caminho (v1—v2—v4) teria uma soma final igual 1005.
Alguma sugestão para melhorar o resultado final?!

1 Resposta

Topicos relacionados