java - Dijkstra 算法 : Printing whole path in console works fine, 无法将其转换为正确的字符串

Question

我目前正在做一个寻路项目，一切都希望最后一点工作正常，我觉得这很愚蠢。

所以我有一个类，它计算网格中两个节点之间的最短路径，包括障碍物。整个算法几乎是从 here 复制粘贴的。因为我自己做不到。但是我构建了一个 GUI 应用程序，您可以在其中创建一个世界然后运行算法，我想在我的网格中直观地表示最短路径。

原始代码中包含两个函数，但它们仅适用于在控制台打印路径。第一个函数在类的主体中 end 接受一个字符串作为结束坐标:

public void printPath(String endName)
{
    if(!graph.containsKey(endName))
    {
        System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
        return;
    }

    graph.get(endName).printPath();
    System.out.println();
}

这调用了在子类中实现的第二个函数:

private void printPath()
    {
        if(this == this.previous)
        {
            System.out.printf("%s", this.name);
        }
        else if(this.previous == null)
        {
            System.out.printf("%s(unreached)", this.name);
        }
        else
        {
            this.previous.printPath();
            System.out.printf("-> %s(%d)", this.name, this.distance);
        }
    }

这工作正常，我得到了这个(示例)的输出:001001-> 002000(14)-> 003000(24)-> 004001(38)-> 004002(48)-> 003003(62) 前三位是行，后三位是列。

现在我正在尝试修改此代码以返回一个字符串，该字符串由所有已访问的节点组成，这些节点只是以一个数字堆叠在一起，以便我稍后可以将其划分并显示在我的网格中。到目前为止，这是我想出的:

public String printPathVisually(String endName)
{
    if(!graph.containsKey(endName))
    {
        System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
        return "Graph doesn't contain end vertex";
    }

    String pathSequence = "";
    pathSequence += graph.get(endName).printPath2();
    System.out.println();
    return pathSequence;
}

以及子类中实现的第二个函数:

private String printPath2()
    {
        String result = "";
        if(this == this.previous)
        {
            result = this.name;
        }
        else if(this.previous == null)
        {
            result = this.name + "(unreached)";
        }
        else
        {
            this.previous.printPath();
            result = this.name;
        }
        return result;
    }

这为我提供了以下结果:003003，这只是结束节点。我真的无法理解为什么会发生这种情况以及我应该如何更改它以提供完整路径。

非常感谢任何帮助或提示!

编辑:Here 是上面显示的示例输出的图像。目标是用某种颜色填充访问过的网格以表示最短路径。

Answer 1

问题在于，在 PrintPath 中，它通过与 previous.printPath 的链递归调用。

在 printPath2 中，您需要做同样的事情，但您还没有更新引用(和周围的逻辑)。这与原始打印输出不太一样(缺少距离)，但大致如下:

private String printPath2()
{
    String result = "";
    if(this == this.previous)
    {
        result = this.name;
    }
    else if(this.previous == null)
    {
        result = this.name + "(unreached)";
    }
    else
    {
        result += this.previous.printPath2();
        result += this.name;
    }
    return result;
}