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. Prim applicato sul grafo

mi da questo risultato

che è ovviamente sbagliato.
Mentre Dijkstra non l'ho proprio provato perchè non riesco a finire di scrivere il codice.
Aiuti?

codice:

package grafi;

import coda.*;
import arrays.*;
import grafo.unionFind.*;
import java.util.*;
import java.lang.*;
import java.io.*;

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) {
			nodo1 = n1;
			nodo2 = n2;
			info = null;
			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(n);
			if(x == null) {
				mapArchi.put(n, ultimoArchi);
				mapArchi.put(nodo2 + nodo1, ultimoArchi);
				Arco nuovo = new Arco(nodo1, nodo2, peso);
				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] = nodoS;
		dist[inodoS] = 0;
		CodaConPriorita coda = FabbricaCodaConPriorita.crea(dimStandard);
		for(int x = 0; x < ultimoNodi; x++) {
			coda.inserisci(x, dist[x]);
			while(!coda.eVuota())
				Nodo u = new Nodo(coda.estraiPrimo());
			double cuv = arrayArchi[u].peso; //weight of the arch between the node u and the node v
			for(int v = 0; v < arrayNodi[u].listeAd.size(); v++) {
				if(dist[u] + cuv < dist[v]) {
					padre[v] = u;
					dist[v] = dist[u] + cuv;
					decreasePriority(v, dist[v], Q);
				}
			}
		}
	}

	public GrafoNonOrientato prim(String nodoS) {
		Integer inodo1 = mapNodi.get(nodoS);
		if(inodo1 == null)
			return null;
		GrafoNonOrientatoListeDiAdiacenza gg = new GrafoNonOrientatoListeDiAdiacenza(ultimoNodi);
		for(int i = 0; i < ultimoNodi; i++)
			visitato[i] = false;
		int inodo = mapNodi.get(nodoS).intValue();
		peso = new double[ultimoNodi];
		padre = new int[ultimoNodi];
		for(int i = 0; i < ultimoNodi; i++) {
			peso[i] = Double.POSITIVE_INFINITY;
			padre[i] = -1;
		}
		coda = FabbricaCodaConPriorita.crea(ultimoNodi);
		coda.inserisci(nodoS, 0.0);
		peso[inodo] = 0;
		while(!coda.eVuota()) {
			nodoS = coda.estraiPrimo();
			String nodoCorrente = arrayNodi[inodo].nome;
			gg.aggiungiNodo(nodoCorrente);
			visitato[inodo] = true;
			for(int i = 0; i < arrayNodi[inodo].listeAd.size(); i++) {
				String nodoVicino = arrayNodi[inodo].listeAd.get(i);
				int iarco = mapArchi.get(nodoVicino + nodoCorrente).intValue();
				int iNodoVicino = mapNodi.get(nodoVicino).intValue();
				if(!visitato[iNodoVicino]) {
					if(peso[iNodoVicino] > arrayArchi[iarco].peso) {
						if(peso[iNodoVicino] == Double.POSITIVE_INFINITY)
							coda.inserisci(nodoVicino, arrayArchi[iarco].peso);
						else
							coda.cambiaPriorita(nodoVicino, arrayArchi[iarco].peso);
						padre[iNodoVicino] = inodo;
						peso[iNodoVicino] = arrayArchi[iarco].peso;
					}
				}
			}
		}
		for(int i = 0; i < padre.length; i++) {
			if(padre[i] != -1) {
				String arcoNome = arrayNodi[padre[i]].nome + arrayNodi[i].nome;
				gg.aggiungiArco(arrayNodi[padre[i]].nome, arrayNodi[i].nome, peso[i], arcoNome);
			}
		}
		return gg;
	} 

        <altri metodi>
}
Grazie