给定一个带权有向图,计算任意两结点间的最短路径。
迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉算法即可求的任意两结点间的最短路径。迪杰斯特拉算法的时间复杂度为O(n^2),因此采用这种方法的时间复杂度为O(n^3)。 但是,迪杰斯特拉算法不允许权值为负数,因此需要使用弗洛伊德算法。 弗洛伊德算法允许权值为负数的边,但不允许回路的路径长度为负数。因为,若回路长度为负数,那么走一次回路,路径长度一定比上一次小,故这个问题就没有意义了。
void Floyd(Map<String,List<ENode>> graph){
// 初始化
Map<String, Map<String, Integer>> dis = new HashMap<>();
Map<String, Map<String, String>> path = new HashMap<>();
// 对dis和path默认初始化
for( String start : graph.keySet() ){
Map<String, Integer> subDis = new HashMap<>();
Map<String, String> subPath = new HashMap<>();
for( String end : graph.keySet() ){
subDis.put( end, Integer.MAX_VALUE );
subPath.put( end, -1 );
}
dis.put( start, subDis );
path.put( start, subPath );
}
// 对dis和path显示初始化
for( Map.Entry<String, List<ENode>> entry : graph ){
String start = entry.getKey();
Map<String, Integer> subDis = dis.get(start);// 二维矩阵dis中的一行
Map<String, String> subPath = path.get(start);// 二维矩阵path中的一行
for( ENode edge : entry.getValue() ){
subDis.put( edge.id, edge.w );
subPath.put( edge.id, start );
}
}
//
for( String k : graph.keySet() ){
for( String i : graph.keySet() ){
for( String j : graph.keySet() ){
if ( dis.get(i).get(k) + dis.get(k).get(j) < dis.get(i).get(j) ) {
dis.get(i).put(j, dis.get(i).get(k) + dis.get(k).get(j) );
path.get(i).put( j, path.get(k).get(j) );
}
}
}
}
}