Floyd算法用于求解任意两点间的最短距离，准许两点间有负的权值，但是一般不准许出现负的环路，其算法复杂度为O(n3)，相对于Dijkstra算法，其计算更为简单，但我自己重新复习的时候，觉得原理越简单，其实理解起来越难，也许你会明白程序怎么写，但为什么这样有时候总容易忘记。
今天闲来无事，复习一下Floyd算法和Warshall算法，将自己写的一个垃圾代码放上去，供自己以后看看，代码质量肯定不高，所以诸位别太。。。。看懂原理就可以。
Warshall算法用来求传递闭包，也是路径存在否，算法处理逻辑和Flyod差不多。
代码如下：
代码
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
public class Warshall {
/**
* 默认尺寸
*/
private static int DEFAULTSIZE = 7;
/**
* 距离数组
*/
private int[][] distances;
/**
* 默认构造函数
*
* @throws IOException
*/
public Warshall() throws IOException {
distances = new int[DEFAULTSIZE][DEFAULTSIZE];
for (int i = 1; i < DEFAULTSIZE; i++) {
for (int j = 1; j < DEFAULTSIZE; j++) {
distances[i][j] = 0;
}
}
InputStream stream = Floyd.class
.getResourceAsStream("/distance2.properties");
DataInputStream in = new DataInputStream(stream);
BufferedReader d = new BufferedReader(new InputStreamReader(in));
String temp = null;
while ((temp = d.readLine()) != null) {
String[] a = temp.split(" ");
distances[Integer.parseInt(a[0])][Integer.parseInt(a[1])] = Integer
.parseInt(a[2]);
}
}
/**
* 计算
*/
public void calculateDistance() {
for (int k = 1; k < 7; k++) {
for (int i = 1; i < 7; i++) {
for (int j = 1; j < 7; j++) {
distances[i][j] = distances[i][j]
| (distances[i][k] & distances[k][j]);
}
}
}
}
public void display() {
for (int i = 1; i < 7; i++) {
for (int j = 1; j < 7; j++) {
if (distances[i][j] != 0) {
System.out.println(i + " --> " + j + " has road");
}
}
}
}
/**
* 运行函数
*
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Warshall warshall = new Warshall();
warshall.calculateDistance();
warshall.display();
}
}
代码
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
public class Floyd {
/**
* 最长路径,修订
*/
private static int LONGESTPATH = 10000;
/**
* 默认尺寸
*/
private static int DEFAULTSIZE = 7;
/**
* 距离数组
*/
private int[][] distances;
/**
* 轨迹数组
*/
private int[][] path;
/**
* 默认构造函数
*
* @throws IOException
*/
public Floyd() throws IOException {
distances = new int[DEFAULTSIZE][DEFAULTSIZE];
path = new int[DEFAULTSIZE][DEFAULTSIZE];
for (int i = 1; i < DEFAULTSIZE; i++) {
for (int j = 1; j < DEFAULTSIZE; j++) {
distances[i][j] = LONGESTPATH;
}
}
// 从文件中读取图中各个节点的距离，如无连线，默认为LONGESTPATH，更为稳妥的办法是得到所有边的最大值，令a>=max(边长)
InputStream stream = Floyd.class
.getResourceAsStream("/distance.properties");
DataInputStream in = new DataInputStream(stream);
BufferedReader d = new BufferedReader(new InputStreamReader(in));
String temp = null;
while ((temp = d.readLine()) != null) {
String[] a = temp.split(" ");
distances[Integer.parseInt(a[0])][Integer.parseInt(a[1])] = Integer
.parseInt(a[2]);
distances[Integer.parseInt(a[1])][Integer.parseInt(a[0])] = Integer
.parseInt(a[2]);
}
}
/**
* 计算距离
*/
public void calculateDistance() {
for (int k = 1; k < 7; k++) {
for (int i = 1; i < 7; i++) {
for (int j = 1; j < 7; j++) {
// 计算距离最小值
// 可以进一步优化，判断distances[i][k]或者distances[k][j]是否为LONGESTPATH，如是可以不进入循环，减少循环次数
if (distances[i][j] > (distances[i][k] + distances[k][j])) {
distances[i][j] = distances[i][k] + distances[k][j];
// 记录轨迹
path[i][j] = k;
}
}
}
}
print(distances);
printPath();
}
/**
* 打印距离
*
* @param distance
* 距离数组
*/
public void print(int[][] distance) {
for (int i = 1; i < DEFAULTSIZE; i++) {
for (int j = i + 1; j < DEFAULTSIZE; j++) {
System.out.println(i + ", " + j + " : " + distance[i][j]);
}
}
}
/**
* 打印轨迹
*/
public void printPath() {
for (int i = 1; i < DEFAULTSIZE; i++) {
for (int j = i + 1; j < DEFAULTSIZE; j++) {
System.out.print(i);
printPath0(i, j);
System.out.print(j);
System.out.println(" ");
}
}
}
/**
* 打印轨迹
*
* @param i
* 始发
* @param j
* 终止
*/
private void printPath0(int i, int j) {
int k = path[i][j];
if (k != 0) {
printPath0(i, k);
System.out.print(" " + k + " ");
printPath0(k, j);
} else {
System.out.print(" ");
}
}
/**
* 运行函数
*
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Floyd floyd = new Floyd();
floyd.calculateDistance();
}
}