java - 使用弗洛伊德算法显示字符串矩阵中的最短路径

Question

因此我能够从字符串矩阵创建正确的最短距离矩阵(其中节点来自 A - z 且边缘标记为 a - z，其中如果边缘存在于两个节点之间，则边缘的权重为 1，否则为无穷)。但我很难显示所采取的路径？这是我的最短路径算法。我试图形成一个连接边缘的数组，但它不起作用。由于矩阵不是 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;
}

Answer 1

尝试在第三个循环中打印

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