Johannes Mols Johannes Mols - 28 days ago 7
Java Question

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

I am currently working on a pathfinding project and everything expect the last bit works fine and I feel very stupid about it.

So I have a class, which calculates me the shortest path between two nodes in a grid including obstacles. The whole algorithm is pretty much copy pasted from here because I just couldn't do it myself. But I built a GUI application where you can create a world and then run the algorithm and I want to visually represent the shortest path in my grid.

There are two functions included in the original code, but they are only good for printing the path in the console. The first function is in the main body of the class end takes a String for the end coordinates:

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


This calls the second function which is implemented in a sub 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);
}
}


This works fine as it is and I get an output of this (example):
001001-> 002000(14)-> 003000(24)-> 004001(38)-> 004002(48)-> 003003(62)

The first three digits are the rows and the last three the columns.

Now I am trying to modify this code to give back a String of all the visited nodes just stacked together in one number so I can later divide it and show it in my grid. This is what I cam up with so far:

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


And the second function implemented in the sub 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;
}


This delivers me the following result:
003003
, which is just the end node. I really can't get my head around why this is happening and how I should change it to give me the full path.

Any help or hint is really appreciated!

Edit: Here
is an image of the example output shown above. The goal is to fill the visited grids in a certain color to represent the shortest path.

Answer

The problem is that in PrintPath, it calls recursively through the chain with previous.printPath.

In printPath2, you need to do the same, but you have not updated the reference (and surrounding logic). This isn't quite the same as the original printout (it missing the distance), but something along the lines of this:

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