使用栈在广度优先搜索中找到最短路径

Question

我正在实现一个最短路径算法来处理我的图表，但是我遇到了困难。在此之前，有很多帖子涵盖了要使用哪个算法，但没有涉及到这么基础的问题。我认为我已经实现了这个问题中的代码。对于每个被遍历的节点，我都会存储一个数组表示我从哪里来。 我不知道如何通过堆栈找到最短路径。

我有以下节点： 我的顶点列表是:

东京，夏威夷，旧金山，洛杉矶，圣地亚哥，芝加哥，纽约，迈阿密，伦敦

寻找从伦敦到夏威夷的路径，我的堆栈看起来像：

000000000 000400000 101100000 033033000 020202000 005500550 000007707 000006066 000000880

一些节点被链接到了圣地亚哥，但其他节点（我想）看起来是正确的。下面是我的实现方式，但我不知道如何通过堆栈并追踪回去。 下面的代码输出路径：夏威夷，夏威夷，夏威夷。它是错误的。

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

- chebyshev

---

广度优先搜索（BFS）实际上使用队列来进行操作。你可以查看任何基本的BFS代码来更清楚地理解它。而深度优先搜索（DFS）则使用栈来以深度优先的方式遍历图，但这并不能保证得到最短路径。 - Fallen

哦，对于加权图（其中所有边的权重不相同），广度优先搜索将无法工作。请改用Dijkstra算法。 - Fallen

@Fallen 实际上，Dijkstra算法是从选定的节点找到所有节点的最短路径；只是想要一个起点和终点之间的路径--但实际上这些想法几乎是相同的。 - artur grzesiak

现在，我只是忽略权重。我不认为我可以使用BFS队列来找到最短路径？我该如何追踪我所走过的路径？ - chebyshev

Answer 1

我建议您实现wikipedia中的算法。当您找到从起点到目标的所有路径时，请尝试向后遍历，比较节点X和其邻居之间的距离。您还可以在这里查看。希望它有所帮助。

- vortex