Ja consegui resolver esse problema, mas aproveitando eu implementei o algoritmo de Dijkstra e está funcionando corretamente mas não consigo encontrar os vértices pelo qual ele passa somente o custo. segue o algoritmo
public class Dijkstra {
final static int INF = 10000;
public static int dijkstra(Graph grafo, int origem, int destino){
int numVertices = grafo.numVertices ();
int dist[] = new int[numVertices];
int vis[] = new int[numVertices];
int parent[] = new int[numVertices];
for (int v = 0; v < numVertices; v++){
dist[v] = INF;
vis[v] = 0;
}
dist[origem] = 0;
int v = origem;//menor atual
while(vis[v] == 0){
//atualiza os vizios de V
Celula ptr = (Celula) grafo.adj[v].primeiro();
while(ptr != null){
int w = ptr.vertice();
int peso = ptr.peso();
relax(v, w, peso, dist);
ptr = (Celula) grafo.adj[v].proximo();
}
vis[v] = 1; //marca como visitado
int w, min_dist = INF;
//achar o vertice w de G que contem a menor distancia
//mas que ainda nao foi processado (vis[w] = 0)
for(w = 0; w < numVertices; w++){
if(vis[w] == 0 && dist[w] < min_dist){
v = w;
min_dist = dist[w];
parent[w] = v;
}
}
}
return dist[destino];
}
public static void relax(int v, int w, int peso, int[] dist) {
if(dist[v] + peso < dist[w] ){
dist[w] = dist[v] + peso;
}
}
}