En ne retournant que les sommets dans le chemin le plus court

Je sais le titre est un peu brouillon, mais je ne sais pas comment l'expliquer mieux.

Ce que je suis en train de faire:

À l'aide d'un graphique trouvé dans un fichier texte, rechercher et imprimer le chemin le plus court (montant minimum de sommets) à partir du sommet A au sommet B.

Remarque: l'utilisation de largeur de recherche, pas de Dijkstra.

Ce que j'ai:

Un travail algorithme qui s'applique BFS sur le graphique, mais pas de bonne façon de réellement l'impression de le chemin le plus court.

Je vais avoir un moment difficile distinguer un sommet dans le chemin le plus court d'un qui est simplement de l'exécuter au moyen de l'algorithme, mais pas dans le chemin le plus court.

Par exemple: Trouver le chemin le plus court entre 0 et 4.
0 se connecte à 1,2 et 3. 1 se connecte à 4.
Mon chemin s'avère être [0,1,2,3,4] au lieu de [0,1,4].

Je n'ai pas été en mesure de trouver tous les threads poser la même question, ou tout au travers de BFS qui comprend cela, alors je ne sais pas si je suis en train de faire ce pour être façon plus difficile qu'elle ne l'est?

Edit: code pour ceux qui pourraient être intéressés (pas sûr du tout si je suis en évitant les cercles?)

Edit 2: Changé la façon dont je conserver mon chemin à une Pile.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

Quelques explications de variables et de méthodes:

v = vertex d'origine

w = cible vertex

g = graphique

vi = normal d'un itérateur qui effectue une itération sur les voisins de v

Merci pour la lecture!

Bonjour, pourriez-vous poster un code source.
Comment est votre graphe représenté dans votre code? Comment éviter de faire des cercles? Il existe assez peu de questions de ce genre qui serait le mieux répondu par vous poster quelques de votre code...
J'ai ajouté un peu de code. Si il manque des infos sur le graphique laissez-moi savoir.
Je pense qu'il manque quelques choses ici. Pour l'un, ne sont pas String objets en Java immuable? A quoi bon changer path dans runBFS faire?
Vous avez tout à fait raison, mon mauvais. J'ai cependant changé de Chaîne pour Pile à l'heure et apporter les modifications appropriées dans le code.

OriginalL'auteur bjrnt | 2011-03-28