3

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:

enter image description here

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;
    }
Community
  • 1
  • 1
chebyshev
  • 141
  • 2
  • 8
  • 2
    BFS works with queue actually. You can have a look at any basic code of bfs to understand it clearly. With stack graph is traversed in depth first fashion which doesn't ensure shortest path actually. – Fallen Nov 17 '13 at 23:02
  • Oh and for weighted graph(where all the edges are not of same weight) bfs won't work. Implement Dijkstra's algorithm instead. – Fallen Nov 17 '13 at 23:06
  • @Fallen actually Dijkstra's finds shortest paths to all nodes from selected node; just wants a path between single pair start-end -- but actually the ideas is almost the same. – artur grzesiak Nov 17 '13 at 23:20
  • right now, I'm just ignoring the weights. I don't think I can use the bfs queue to find the shortest path? how do i track where i've been? – chebyshev Nov 17 '13 at 23:29

1 Answers1

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.

Community
  • 1
  • 1
vortex
  • 1,048
  • 1
  • 10
  • 17