Grafo non orientato: algoritmi di Prim e Dijkstra

di il
3 risposte

Grafo non orientato: algoritmi di Prim e Dijkstra

Ciao, ho fatto questa classe sui grafi non orientati rappresentati mediante liste di adiacenza ed i cui nodi del grafo sono stringhe. I metodi vanno tutti eccetto l'algoritmo di Prim e Dijkstra.
Essendo Prim una modifica di Dijkstra vorrei risolvere principalmente Dijkstra.

public class GrafoNonOrientatoListeDiAdiacenza implements GrafoNonOrientato {
	static final int dimStandard = 100;
	private static double INFINITO = Double.MAX_VALUE;
	Nodo[] arrayNodi;
	Arco[] arrayArchi;	
	int ultimoNodi;
	int ultimoArchi; 
	boolean[] visitato;
	double[] peso;
	int[] padre;
	CodaConPriorita coda;
	UnionFindInt unionFind;
	Hashtable<String, Integer> mapNodi; 
	Hashtable<String, Integer> mapArchi;	
	private static Random gen = new Random();

	private class Arco {		
		String nodo1;
		String nodo2;
		String info;
		double peso;
		
		private Arco()	{
			nodo1 = "";
			nodo2 = "";
			info = null;
			peso = 0;
		}
		
		private Arco(String n1, String n2, double peso, String info) {
			nodo1 = n1;
			nodo2 = n2;
			this.info = info;
			this.peso = peso;
		}								
	}
	
	private class Nodo {
		String nome;
		LinkedList<String> listeAd;
		
		private Nodo() {
			nome = "";
			listeAd = new LinkedList<String>();
		}
		
		private Nodo(String nome) {
			this.nome = nome;
			listeAd = new LinkedList<String>();
		}			
	}
	
	public GrafoNonOrientatoListeDiAdiacenza() {
		arrayNodi = new Nodo[dimStandard];
		arrayArchi = new Arco[dimStandard];		
		ultimoNodi = 0;
		ultimoArchi = 0;
		visitato = new boolean[dimStandard];
		peso = new double[dimStandard];
		padre = new int[dimStandard];
		coda = FabbricaCodaConPriorita.crea(dimStandard);
		unionFind = FabbricaUnionFindInt.crea(dimStandard);			
		mapNodi = new Hashtable<String, Integer>(dimStandard);
		mapArchi = new Hashtable<String, Integer>(dimStandard);
	}
	
	public GrafoNonOrientatoListeDiAdiacenza(int n) {
		arrayNodi = new Nodo[n];
		arrayArchi = new Arco[n];		
		ultimoNodi = 0;
		ultimoArchi = 0;
		visitato = new boolean[n];
		peso = new double[n];
		padre = new int[n];
		coda = FabbricaCodaConPriorita.crea(n);
		unionFind = FabbricaUnionFindInt.crea(n);			
		mapNodi = new Hashtable<String, Integer>(n);
		mapArchi = new Hashtable<String, Integer>(n);
	}
		
	public int numNodi() {
		return ultimoNodi;
	}
	
	public int numArchi() {
		return ultimoArchi;
	}		
	
	public void aggiungiNodo(String v) {
		Integer x = mapNodi.get(v); 
		if(x == null) { 
			mapNodi.put(v, ultimoNodi);
			arrayNodi[ultimoNodi] = new Nodo(v);
			ultimoNodi++;
		}
		else 
			System.out.println("Nodo gia' esistente");
	}
	
	public void aggiungiArco(String nodo1, String nodo2, double peso, String nome) {
		Integer x1 = mapNodi.get(nodo1); 
		Integer x2 = mapNodi.get(nodo2); 
		if((x2 != null) && (x1 != null)) { 
			String n = nodo1 + nodo2; 
			Object x = mapArchi.get(nome); 			
                        if(x == null) { 
				mapArchi.put(n, ultimoArchi); 
				mapArchi.put(nodo2 + nodo1, ultimoArchi);
				Arco nuovo = new Arco(nodo1, nodo2, peso, nome); 
				arrayArchi[ultimoArchi] = nuovo;
				int ind = mapNodi.get(nodo1).intValue(); 
				int ind1 = mapNodi.get(nodo2).intValue(); 
				arrayNodi[ind].listeAd.add(nodo2); 
				arrayNodi[ind1].listeAd.add(nodo1);
				ultimoArchi++; 
			}
			else 
				System.out.println("Arco gia' esistente");
		}
		else 
			System.out.println("Nodi inesistenti");	
	}
	
	public void dijkstra(String nodoS) {
		double[] dist = new double[dimStandard];
		for(int x = 0; x < ultimoNodi; x++) { 
			dist[x] = INFINITO; 
			padre[x] = -1;
		}		
		Integer inodoS = mapNodi.get(nodoS);
		padre[inodoS] = inodoS; 
		dist[inodoS] = 0;
		CodaConPriorita coda = FabbricaCodaConPriorita.crea(dimStandard);
		for(int x = 0; x < ultimoNodi; x++) { 
			String j = arrayNodi[x].nome;
			coda.inserisci(j, dist[x]);
		}		
		while(!coda.eVuota()) {
			Nodo u = new Nodo(coda.estraiPrimo()); //estraggo il primo cioè quello con distanza minima
			Integer iU = mapNodi.get(u);
			for(int v = 0; v < arrayNodi[iU].listeAd.size(); v++) { //for each(Nodo v adiacente a u)
				double cuv = pesoArco(u.nome, arrayNodi[v].nome); 
				if(dist[iU] + cuv < dist[v]) {
					padre[v] = iU; 
					dist[v] = dist[iU] + cuv;
					coda.cambiaPriorita(arrayNodi[v].nome, dist[v]); //decreasePriority(v, dist[v], coda);
				}
			}
		} 
	}

	public double pesoArco(String arco1, String arco2) {
		for(int i = 0; i < ultimoArchi; i++) {
			String nome1 = arrayArchi[i].nodo1 + arrayArchi[i].nodo2;
			String nome2 = arrayArchi[i].nodo2 + arrayArchi[i].nodo1;
			if(arrayArchi[i].info.compareTo(nome1) == 0 || arrayArchi[i].info.compareTo(nome2) == 0)
				return arrayArchi[i].peso;
		}
		throw new IllegalArgumentException();
	}
        
        <altri metodi>
}
Dijkstra non riesco a testarlo poichè il metodo pesoArco non funziona. Tale metodo dovrebbe cercare nell'array di archi quello con i due estremi chiamati arco1 e arco2 e restituire il peso di quest'arco.
Quando vado a provare questo singolo metodo mi da errore dicendo che non lo trova. Eppure è dichiarato pubblico ed è inserito nella mia interfaccia. Dov'è il problema?
Grazie

3 Risposte

Devi accedere o registrarti per scrivere nel forum
3 risposte