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;
    }
4
  • 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, 2013 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, 2013 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. Nov 17, 2013 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, 2013 at 23:29

1 Answer 1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.