Dijkstra 算法：在控制台中打印整个路径工作正常，无法将其放入正确的字符串中

Question

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

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

原代码中有两个函数，但只对在控制台打印路径有用。第一个函数在主体部分class end 取一个String为结束坐标：

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

这调用了在子class中实现的第二个函数：

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

和子class中实现的第二个函数：

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

Dijkstra 算法：在控制台中打印整个路径工作正常，无法将其放入正确的字符串中

Dijkstra Algorithm: Printing whole path in console works fine, can't get it into a proper String

java

algorithm

dijkstra