思路
适用于矩阵算路，将m个节点的图，组成矩阵m*m，然后从第一个点开始，依次遍历矩阵中值，比较两两节点的权重和经过第一个点的值的大小，更新矩阵；
例如，第i行，第k列的值为V(i,k)(i∈(0，m),k∈(0,m),i!=k)，将此值与V(i,1)+V(1,k)比较，较小值作为新的V(i,k);
当第一个点全都与矩阵值比较更新之后，开始第二个点的比较，依次类推；
当所有点都比较完，此矩阵即为所有两两点之间的权重最小值。
代码
public class Floyd {
private final List<GraphNode> graph;
private final String startNodeId;
private final String endNodeId;
private TraverseNode[][] matrixNodes;
private Map<Integer, GraphNode> dicNodes;
public Floyd(List<GraphNode> graph, String startNodeId, String endNodeId) {
List<GraphNode> copyGraph = new ArrayList<>();
graph.forEach(graphNode -> {
GraphNode copy = graphNode.copy();
copyGraph.add(copy);
});
this.graph = copyGraph;
this.startNodeId = startNodeId;
this.endNodeId = endNodeId;
}
public CalcResult calcShortPath(boolean needPrint) {
init();
CalcResult result = findPath();
if (needPrint && result != null) {
result.getResultPath().forEach(System.out::println);
System.out.println("weight:" + result.getWeight());
}
return result;
}
private void init() {
// 组建矩阵
matrixNodes = new TraverseNode[this.graph.size()][this.graph.size()];
dicNodes = new HashMap<>();
for (int i = 0; i < this.graph.size(); i++) {
dicNodes.put(i, this.graph.get(i));
}
for (int i = 0; i < this.graph.size(); i++) {
for (int k = 0; k < this.graph.size(); k++) {
GraphNode startNode = dicNodes.get(i);
GraphNode endNode = dicNodes.get(k);
matrixNodes[i][k] = new TraverseNode();
if (i == k) {
matrixNodes[i][k].setWeight(0);
matrixNodes[i][k].setPreNodeId(startNode.getNodeId());
continue;
}
matrixNodes[i][k].setWeight(startNode.getNearNodeValueTable().getOrDefault(endNode.getNodeId(), Integer.MAX_VALUE));
matrixNodes[i][k].setPreNodeId(startNode.getNearNodeValueTable().containsKey(endNode.getNodeId()) ?
startNode.getNodeId() : null);
}
}
}
private CalcResult findPath() {
for (int k = 0; k < this.graph.size(); k++) {
for (int i = 0; i < this.graph.size(); i++) {
for (int j = 0; j < this.graph.size(); j++) {
if ((long) matrixNodes[i][j].getWeight() > ((long) matrixNodes[i][k].getWeight() + (long) matrixNodes[k][j].getWeight())) {
matrixNodes[i][j].setPreNodeId(dicNodes.get(k).getNodeId());
matrixNodes[i][j].setWeight(matrixNodes[i][k].getWeight() + matrixNodes[k][j].getWeight());
}
}
}
}
Integer startIndex = -1;
Integer endIndex = -1;
for (Map.Entry<Integer, GraphNode> entry : dicNodes.entrySet()) {
if (Objects.equals(entry.getValue().getNodeId(), startNodeId)) {
startIndex = entry.getKey();
}
if (Objects.equals(entry.getValue().getNodeId(), endNodeId)) {
endIndex = entry.getKey();
}
if (startIndex != -1 && endIndex != -1) {
break;
}
}
if (startIndex == -1 || endIndex == -1) {
System.out.println("error!");
return null;
}
return tidyUpPath(startIndex, endIndex);
}
private CalcResult tidyUpPath(Integer startIndex, Integer endIndex) {
List<String> path = new ArrayList<>();
Integer curIndex = endIndex;
path.add(endNodeId);
Integer weight = matrixNodes[startIndex][curIndex].getWeight();
while (curIndex != null && !Objects.equals(curIndex, startIndex)) {
String nodeId = matrixNodes[startIndex][curIndex].getPreNodeId();
if (nodeId == null) {
curIndex = null;
break;
}
path.add(nodeId);
for (Map.Entry<Integer, GraphNode> entry : dicNodes.entrySet()) {
if (Objects.equals(entry.getValue().getNodeId(), nodeId)) {
curIndex = entry.getKey();
break;
}
}
}
if (curIndex == null) {
System.out.println("no path!");
return null;
}
path.add(startNodeId);
path = path.stream().distinct().collect(Collectors.toList());
Collections.reverse(path);
CalcResult calcResult = new CalcResult();
calcResult.setResultPath(path);
calcResult.setWeight(weight);
return calcResult;
}
}