WarShall算法--图的传递闭包（进一步演变成flayd算法）

package graph;

import java.util.ArrayList;
import java.util.List;

public class WarshallTest {

public static void main(String[] args) {

Warshall w = new Warshall(8);
w.addVertex("a");
w.addVertex("b");
w.addVertex("c");
w.addVertex("d");
w.addVertex("e");
w.addVertex("f");
w.addVertex("g");

w.addEdge(0, 2);
w.addEdge(1, 0);
w.addEdge(1, 4);
w.addEdge(3, 4);
w.addEdge(4, 2);
w.addEdge(2, 5);
w.addEdge(5, 6);

w.printMatrix();

w.doWarshall();

w.printMatrix();
}
}

class Warshall {

private List<Vertex> vertexList;
private int[][] matrix = null;
private int maxSize = 20;

public Warshall(int maxSize) {
vertexList = new ArrayList<Vertex>(maxSize);
matrix = new int[maxSize][maxSize];
this.maxSize = maxSize;
}

// 增加顶点
public void addVertex(String label) {
if (isFull())
throw new ArrayIndexOutOfBoundsException("数组已经满了");
vertexList.add(new Vertex(label));
}

private boolean isFull() {
return vertexList.size() == maxSize;
}

// 增加边
public void addEdge(int start, int end) {
int size = getSize();
if (start >= size || end >= size)
throw new ArrayIndexOutOfBoundsException();

this.matrix[start][end] = 1;
}

// 执行算法
public void doWarshall() {
int len = getSize();
// 考察每一行
for (int x = 0; x < len; x++) {
// 考察行中的每个单元
for (int y = 0; y < len; y++) {
if (matrix[x][y] == 1) {
// 考察列x的每一个单元
for (int z = 0; z < len; z++) {
if (matrix[z][x] == 1) {
matrix[z][y] = 1;
}
}
}
}
}
}

private int getSize() {
return this.vertexList.size();
}

// 打印邻接矩阵
public void printMatrix() {
System.out.println();
int len = getSize();
for (int i = 0; i < len; i++) {
for (int k = 0; k < len; k++) {
System.out.print(matrix[i][k]);
}
System.out.println();
}
}

/**
 * 顶点
 * 
 * @author admin
 *
 */
class Vertex {
private String label;
private boolean isVisited;

public Vertex(String label) {
this.label = label;
this.isVisited = false;
}

public String getLabel() {
return label;
}

public void setLabel(String label) {
this.label = label;
}

public boolean isVisited() {
return isVisited;
}

public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}

}

}

二、由上面的Warshall算法直接演变成Floyd算法

package graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class WarshallTest {

public static void main(String[] args) {
Warshall w = new Warshall(8);
w.addVertex("a");
w.addVertex("b");
w.addVertex("c");
w.addVertex("d");
w.addVertex("e");
w.addVertex("f");
w.addVertex("g");

w.addEdge(0, 2, 10);
w.addEdge(1, 0, 20);
w.addEdge(1, 4, 30);
w.addEdge(3, 4, 20);
w.addEdge(4, 2, 40);
w.addEdge(2, 5, 60);
w.addEdge(5, 6, 10);
w.addEdge(4, 6, 40);

w.printMatrix();

w.doWarshall();

w.printMatrix();
}
}

class Warshall {

private List<Vertex> vertexList;
private int[][] matrix = null;
private int maxSize = 20;

public Warshall(int maxSize) {
vertexList = new ArrayList<Vertex>(maxSize);
matrix = new int[maxSize][maxSize];
this.maxSize = maxSize;
}

// 增加顶点
public void addVertex(String label) {
if (isFull())
throw new ArrayIndexOutOfBoundsException("数组已经满了");
vertexList.add(new Vertex(label));
}

private boolean isFull() {
return vertexList.size() == maxSize;
}

// 增加边
public void addEdge(int start, int end, int weigth) {
int size = getSize();
if (start >= size || end >= size)
throw new ArrayIndexOutOfBoundsException();

this.matrix[start][end] = weigth;
}

// 执行算法
public void doWarshall() {

int len = getSize();
int temp1 = -1;
int temp2 = -1;
// 考察每一行
for (int x = 0; x < len; x++) {
// 考察行中的每个单元
for (int y = 0; y < len; y++) {
temp1 = matrix[x][y];
if (temp1 > 0) {
// 考察列x的每一个单元
for (int z = 0; z < len; z++) {
temp2 = matrix[z][x];
if (temp2 > 0) {
if(matrix[z][y] == 0){
matrix[z][y] = temp1 + temp2;
}else if(temp1+temp2 < matrix[z][y]){
matrix[z][y] = temp1 + temp2;
}
}
}
}
}
}
}


// 执行算法
public void doWarshall2() {
int len = getSize();
int temp1 = -1;
int temp2 = -1;
// 考察每一行
for (int x = 0; x < len; x++) {
// 考察行中的每个单元
for (int y = 0; y < len; y++) {
temp1 = matrix[x][y];
if (temp1 > 0) {
// 考察列x的每一个单元
for (int z = 0; z < len; z++) {
temp2 = matrix[z][x];
if (temp2 > 0) {
if(matrix[z][y] == 0){
matrix[z][y] = temp1 + temp2;
}else if(temp1+temp2 < matrix[z][y]){
matrix[z][y] = temp1 + temp2;
}
}
}
}
}
}
}

private int getSize() {
return this.vertexList.size();
}

// 打印邻接矩阵
public void printMatrix() {
System.out.println();
int len = getSize();
for (int i = 0; i < len; i++) {
for (int k = 0; k < len; k++) {
System.out.print(matrix[i][k]+";    ");
}
System.out.println();
}
}

/**
 * 顶点
 * 
 * @author admin
 *
 */
class Vertex {
private String label;
private boolean isVisited;

public Vertex(String label) {
this.label = label;
this.isVisited = false;
}

public String getLabel() {
return label;
}

public void setLabel(String label) {
this.label = label;
}

public boolean isVisited() {
return isVisited;
}

public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}

}

}

结果：