CODEWITHSUNDEEP
javapathshortest
Scarlett
Scarlett

Reputation: 1

Display shortest path in a String matrix using Floyd's Algorithm

so I am able to create the correct shortest distance matrix from a String matrix (where nodes are from A - z and edges labelled a - z where the weight on an edge is 1 if it exists between two nodes, else it is infinity). But I am struggling to display the path taken? Here is my shortest path algorithm. I have tried to form an array which concatenates the edges, but it doesn't work. Struggling to find another way since the matrix isn't an int. 

    public String[][] shortestPath(String[][] graph, int[][] dist)
{

    String[][] path = new String[graph.length][graph.length];
    //Shortest Path
    int i, j, k;
    for ( k = 0; k < graph.length; k++) { 


        for ( i = 0; i < graph.length; i++) { 

            for ( j = 0; j < graph.length; j++) { 

                if (dist[i][k] + dist[k][j] < dist[i][j] ) {
                    dist[i][j] = dist[i][k] + dist[k][j]; 
                    graph[i][j] = "-" 
                    + graph[i][k].charAt(graph[i][k].length() - 1);

                    path[i][j] += graph[i][k] + graph[k][j];

                }

                else {
                    path[i][j] += graph[i][j]+ graph[j][i];                    }


            } 

        } 


    }//end of main for loop 




    return graph;
}

Upvotes: 0

Views: 181

Answers (1)

0xh3xa
0xh3xa

Reputation: 4857

Try to print in the third-loop

    for (j = 0; j < graph.length; j++) {

        if (dist[i][k] + dist[k][j] < dist[i][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
            graph[i][j] = "-" + graph[i][k].charAt(graph[i][k].length() - 1);

            path[i][j] += graph[i][k] + graph[k][j];

        } else {
            path[i][j] += graph[i][j] + graph[j][i];
        }
        System.out.println(path[i][j]);
    }

Upvotes: 0

Related Questions