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

Question

所以我能够从字符串矩阵创建正确的最短距离矩阵(其中节点来自 A - z，边缘标记为 a - z，如果边缘上的权重存在于两个节点之间，则为 1，否则它是无穷大(。但我正在努力展示所走的路？这是我的最短路径算法。我试图形成一个连接边缘的数组，但它不起作用。努力寻找另一种方式，因为矩阵不是整数。

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