Mit einem stack zu finden, der kürzeste Weg in die Breite zuerst-Suche

Ich bin eine harte Zeit der Umsetzung ein shortest-path-Algorithmus für meine Grafik. Viele Beiträge auf dieser Abdeckung, welcher Algorithmus zu verwenden ist, aber nichts grundlegendes. Ich glaube, ich habe umgesetzt der code von dieser Frage. Für jeden Knoten durchzogen ist, Speicher ich ein array, der angibt, wo ich habe kommen von. Ich bin mir nicht sicher, wie die Arbeit durch den Stapel, um den kürzesten Weg zu finden.

Habe ich die folgenden Knoten:

Meine Liste der Scheitelpunkte ist :

Tokio , hawaii, san francisco, los angeles, san diego, chicago, new york, miami, london

Suchen für den Weg von London nach Hawaii, mein stack endet auf der Suche wie:

000000000

000400000

101100000

033033000

020202000

005500550

000007707

000006066

000000880

irgendwie Tokio bekommt, verbunden mit San Diego, aber der rest ( denke ich) korrekt aussieht. Unten ist meine Umsetzung, aber ich weiß nicht, wie zu laufen Sie durch die Stapel-und trace-mein Weg zurück. Der untenstehende code gibt den Pfad: hawaii, hawaii, hawaii. Es ist falsch.

 public static List<string> ShortestPath(Graph graph, string src, string dest)
    {
        List<string> path = new List<string>();

        List<string> city_ref = graph.GetVertices();
        Queue<string> Visited = new Queue<string>();
        Queue<string> ToVisit = new Queue<string>();
        Stack<int[]> stack = new Stack<int[]>();

        ToVisit.Enqueue(src);
        while (ToVisit.Count != 0)
        {
            string V = ToVisit.Dequeue();
            if (Visited.Contains(V))
                ;
            else
            {
                int[] previous = new int[city_ref.Count];
                for (int i = 0; i < graph.Neighbors(V).Count; i++)
                {
                    //previous[i] = -1;
                    ToVisit.Enqueue(graph.Neighbors(V)[i]);
                    int pointer = city_ref.IndexOf(graph.Neighbors(V)[i]);
                    previous[pointer] = city_ref.IndexOf(V);
                }

                stack.Push(previous);
                Visited.Enqueue(V);
            }

        }

        int path_val = city_ref.IndexOf(dest);
        while(stack.Count != 0)
        {
            int[] i = stack.Pop();

            for (int p = 0; p < i.Length; p++)
            {
                if (i[p] == path_val)
                {
                    path.Add(city_ref[i[p]]);
                    path_val = i[p];
                }
            }

        }
        return path;
    }