Using a stack to find shortest path in breadth first search

Question

I'm having a tough time implementing a shortest path algorithm for my graph. A lot of posts on this cover which algorithm to use, but nothing this basic. I think I've implemented the code from this question. For each node traversed, I store an array indicating where I've come from. I'm not sure how to work through the stack to find the shortest path.

I have the following nodes:

My list of vertices is :

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

Looking for the path from London to Hawaii, my stack ends up looking like:
000000000
000400000
101100000
033033000
020202000
005500550
000007707
000006066
000000880

somehow tokyo gets linked to San Diego, but the rest ( I think) looks correct. Below is my implementation, but I don't know how to run through the stack and trace my way back. The below code outputs the path: hawaii, hawaii, hawaii. It's wrong.

 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;
    }

Answer 1

I would suggest you to implement the algorithm from wikipedia. When you find all the paths from start to goal, try to traverse backwards, comparing the distance between node X and its neighbors. Also you can look here. Hope it helps.