Estoy atascado en el algoritmo de Dijkstra para un grafo dirigido con un vértice de origen y uno de destino (con sus respectivos pesos o costos). La cosa es que tengo que hallar el camino mas corto (valga la redundancia), pero solo he logrado que el recorrido vaya por el camino mas corto de cada nodo, no de todo el grafo desde el origen hasta el destino. La gracia es usar algo parecido al BFS pero adaptarlo para Dijkstra. Se que tengo que comparar las sumas de todos los caminos que llegan hasta el destino pero no hallo la manera de hacerlo. Tambien tengo entendido que se puede utilizar una cola de prioridad pero la verdad que no tengo idea como o en que parte.
Mi código es el siguiente:
public void caminoCortoBFS (String A, String B, JTextArea jta){
desmarcarTodos();
ordenarVerticesAlf(); Arco a;
float distanciatotal=0;
Vertice v = buscarVertice(A), w;
LinkedList <Vertice> C;
C=new LinkedList<Vertice>();
C.add(v);
v.marcado=true; jta.append("Camino mas corto de " + A + "a " + B + " es: ");
do{
v = C.pop();
jta.append(v.getNombre() + " ");
for (int i = 0; i < v.LArcos.dim(); i++) {
a = (Arco) v.LArcos.getElem(i);
if(a.getCosto() == minDistancia(v)){
distanciatotal+=minDistancia(v);
w=buscarVertice(a.getNombreVertD());
if(w.nombre.equals(B)){
jta.append(w.getNombre() + " " + "\n");
jta.append("Distancia total = " + distanciatotal);
return;}
if (!w.marcado) {
C.add(w);
w.marcado=true;
}
}
}
}while (!C.isEmpty());
}
private float minDistancia(Vertice A){
float distMinima=99999; Arco a;
for(int i=0; i<A.LArcos.dim(); i++){
a = (Arco) A.LArcos.getElem(i);
if(a.getCosto()<distMinima)
distMinima=a.getCosto();
}
return distMinima;
}
Y como resultado para el siguiente grafo:
Me da como resultado poniendo como vértices Origen A - Destino D :
A -> C -> E -> D
Cuando deberia ser A -> B -> D
Se que esta fatal, pero agradecería cualquier ayuda que pudieran darme.