Hola, como están?

Bueno, estoy tratando de implementar el algoritmo de Dijkstra (tambien conocido como camino minimo con pesos) en java. Bien la cosa es que es que estoy usando un monticulo binario para que vaya guardando los nodos. Pero no logro dar con la solucion exacta.

Aqui les dejo las clases:

/////// Esta Representa cada Nodo //////////
final class Vertice {

String nombre; //el nombre lo identifica
List<Arco> listaAdj;
int coste; // coste desde el vertice inicial despues de ejecutar el algoritmo (sin pesos y Dijkstra)
Vertice anterior; // vertice previo en camino mínimo (sin pesos y Dijkstra)
int extra;// variable extra utilizada en algoritmos, para ver, por ejemplo si ha sido visitado el vertice, podria ser boolean

Vertice( String nom )
{
nombre = nom;
listaAdj = new LinkedList<Arco>( );
resetear( );
}

void resetear( )
{
coste = Grafo.INFINITO;
anterior = null;
extra = 0;
}
@Override
public boolean equals(Object o)
{
if( o instanceof Vertice)
{
Vertice v = (Vertice)o;
return v.nombre.equals(nombre);
}
else
return false;
}
@Override
//codigo generado
public int hashCode() {
int hash = 3;
hash = 23 * hash + (this.nombre != null ? this.nombre.hashCode() : 0);
return hash;
}
}

//////// Esta es el arco entre cada nodo /////////

class Arco {

Vertice destino; // Segundo
int costo; // costo de la arista, 1 si es sin pesos

Arco(Vertice d, int c) {
destino = d;
costo = c;
}

@Override
public boolean equals(Object o) {
if (o instanceof Arco) {
Arco a = (Arco) o;
if (a.destino.equals(destino) && a.costo == costo) {
return true;
} else {
return false;
}
} else {
return false;
}
}

@Override
//codigo generado
public int hashCode() {
int hash = 7;
hash = 73 * hash + (this.destino != null ? this.destino.hashCode() : 0);
hash = 73 * hash + this.costo;
return hash;
}
}

/////////// Esta es MonticuloBinario que hereda de ColaDePrioridad ////////////

public class MonticuloBinario <AnyType extends Comparable<? super AnyType>> implements ColaDePrioridad<AnyType>
{
private AnyType [] arreglo;
private int tamanio;

public MonticuloBinario()
{
this(11);
}
public MonticuloBinario(int tam)
{
arreglo = (AnyType []) new Object[tam];
tamanio = 0;
}

@Override
public void insertar(AnyType x) {

if(tamanio + 1 == arreglo.length)
duplicar();

int hueco = ++tamanio;
arreglo[0] = x;
//FILTRADO ASCENDENTE
while(x.compareTo(arreglo[hueco / 2]) < 0)
{
arreglo [hueco] = arreglo [hueco / 2];
hueco = hueco / 2;
}
arreglo[hueco] = x;
}

private void duplicar()
{
AnyType[] aux = (AnyType[]) new Comparable[arreglo.length * 2];

System.arraycopy(arreglo, 0, aux, 0, arreglo.length);

arreglo = aux;
}

@Override
public AnyType minimo() {

if(esVacia())
return null;
return arreglo[1];
}

@Override
public AnyType eliminarMin() {
if(esVacia())
return null;
AnyType tmp = arreglo[1];
arreglo[1] = arreglo[tamanio--];
filtradoDescendente(1);
return tmp;
}

private void filtradoDescendente(int hueco)
{
int hijo;
AnyType tmp = arreglo[ hueco ];

for(; hueco * 2 <= tamanio; hueco = hijo )
{
hijo = hueco * 2;
if( hijo != tamanio && arreglo[ hijo + 1 ].compareTo( arreglo[ hijo ] ) < 0)
hijo++;
//en hijo tengo el menor
if( arreglo[ hijo ].compareTo( tmp ) < 0 )
arreglo[ hueco ] = arreglo[ hijo ];
else
break;

}
arreglo[ hueco ] = tmp;
}

@Override
public boolean esVacia() {
return tamanio == 0;
}

@Override
public void vaciar() {
tamanio = 0;
}

@Override
public int size() {
return tamanio;
}
}

//////////// Esta es la clase grafo donde está el algoritmo en si ///////////

public class Grafo {

public static final int INFINITO = Integer.MAX_VALUE;
private Map<String, Vertice> verticesMapa;

public Grafo() {
verticesMapa = new HashMap<String, Vertice>();
}

/**
* Agrega un nuevo vertice al grafo
* (al mapa de vertices) siempre que el nombre
* no exista, en caso de que ya exista un vertice
* con el nombre tira la excepcion.
* @param nombre nombre del nuevo vertice
* @throws ElementoDuplicado en caso de que exista un vertice con el mismo nombre en el mapa
*/
public void agregarVertice(String nombre) throws ElementoDuplicado {
Vertice v = verticesMapa.get(nombre);
if (v == null) {
v = new Vertice(nombre);
verticesMapa.put(nombre, v);
} else {
throw new ElementoDuplicado("Ya existe vertice con ese nombre");
}
}

/**
* Elimina el vértice así como todos los arcos asociados a el
* en caso de que el vertice no existe lanza una excepcion.
* @param nombre nombre del vertice a eliminar
* @throws ElementoNoEncontrado en caso de que no exista un vertice con ese nomnbre en el mapa
*/
public void eliminarVertice(String nombre) throws ElementoNoEncontrado {
Vertice v = verticesMapa.get(nombre);
if (v == null) {
throw new ElementoNoEncontrado("No existe vertice con ese nombre ");
}

verticesMapa.remove(nombre);

Vertice w;
for (Map.Entry<String, Vertice> entrada : verticesMapa.entrySet()) {
w = entrada.getValue();
for (Arco a : w.listaAdj) {
if (a.destino.equals(v)) {
w.listaAdj.remove(a);
}
}
}
}

/**
* Agrega nuevo arco al grafo.
* Si no existe algun vertice con esos nombres los crea y
* agrega al mapa.
* @param nombreOrigen nombre del vertice origen
* @param nombreDestino nombre del vertice destino
* @param costo asociado a la arista (si es sin pesos debe ser 1)
* @throws ElementoDuplicado en caso de tener dos arcos identicos
*/
public void agregarArco(String nombreOrigen, String nombreDestino, int costo) throws ElementoDuplicado {
Vertice v = getVertice(nombreOrigen);
Vertice w = getVertice(nombreDestino);
Arco a = new Arco(w, costo);
if (v.listaAdj.contains(a)) {
throw new ElementoDuplicado("Ya existe un arco identico");
} else {
v.listaAdj.add(a);
}
}

public void eliminarArco(String origen, String destino, int costo) throws ElementoNoEncontrado {
Vertice v = verticesMapa.get(origen);
Vertice w = verticesMapa.get(destino);
if (v == null || w == null) {
throw new ElementoNoEncontrado("no existe origen o destino");
}
Arco a = new Arco(w, costo);
if (v.listaAdj.remove(a))
//llamo al eliminar de la lista que devuelve true si lo elimina
//en este caso lo eliminó sin problemas, no hago nada
; else {
throw new ElementoNoEncontrado("Arco a eliminar no existe");
}
}

/**
* Rutina publica que imprime el camino y el costo total,
* tiene en cuenta el caso de nodos destino inalcanzable.
* llama recursivamente para imprimir camino hasta nombreDestino
* DESPUES qye el algoritmo de camino mínimo ha sido ejecutado.
*/
public void imprimirCamino(String nombreDestino) throws ElementoNoEncontrado {
Vertice w = verticesMapa.get(nombreDestino);
if (w == null) {
throw new ElementoNoEncontrado("Vertice destino no encontrado");
} else if (w.coste == INFINITO) {
System.out.println(nombreDestino + " es inalcanzable");
} else {
System.out.print("(Costo es: " + w.coste + ") ");
imprimirCamino(w);
System.out.println();
}
}

/**
* Rutina recursiva para imprimir camino mínimo
* DESPUES que se ejecute el algoritmo de caminos mínimos.
*/
private void imprimirCamino(Vertice dest) {
if (dest.anterior != null) {
imprimirCamino(dest.anterior);
System.out.print(" -> ");
}
System.out.print(dest.nombre);
}

/**
* SI el nombre de vertice no existe lo crea agregandolo al mapa
* de otra manera devuelve el vertice por nombre
*/
private Vertice getVertice(String verticeNombre) {
Vertice v = verticesMapa.get(verticeNombre);
if (v == null) {
v = new Vertice(verticeNombre);
verticesMapa.put(verticeNombre, v);
}
return v;
}

/**
* Inicializa los vertices antes de correr al algoritmo de caminos mínimos.
*/
private void limpiarTodo() {
for (Vertice v : verticesMapa.values()) {
v.resetear();
}
}

/**
* Verifica si el grafo es vacio, si carece de vertices
* @return true si es vacio, false en caso contrario.
*/
public boolean esVacio() {
return verticesMapa.isEmpty();
}

/**
* Algoritmo de caminos mínimos sin pesos
* :)
*/
public void sinPesos(String nombreInicio) throws ElementoNoEncontrado {
Vertice inicio = verticesMapa.get(nombreInicio);
if (inicio == null) {
throw new ElementoNoEncontrado("Vertice Inicial no encontrado");
}

limpiarTodo();

}

/**
* Algoritmo de dijkstra
* :)
*/
public void dijkstra(String nombreInicio) throws ElementoNoEncontrado {

}
}

///////////

Bueno, saludos y disculpens si quedo muy largo ^^