Floyd - Warshall算法

顶点

public class Vertex {String name;List<Edge> edges;// 拓扑排序相关int inDegree;int status; // 状态 0-未访问 1-访问中 2-访问过，用在拓扑排序
// dfs, bfs 相关boolean visited;//是否被访问过
// 求解最短距离相关private static final int INF = Integer.MAX_VALUE;int dist = INF;Vertex prev = null;public Vertex(String name){this.name = name;}public String getName{return name;}@Override public String toString(){return name + '('+dist+')';}@Overridepublic boolean euqals(Object o){if(this == o)return true;if(0==null||getClass()!=o.getClass())return false;Vertex vertex = (Vertex) o;return Objexts.equals(name,Vertex.name);}@Overridepublic int hashCode(){return name!=null?name.hashCode():0;}

边

public class Edge {
Vertex linked;int weight;
public Edge(Vertex linked) {this(linked, 1);}
public Edge(Vertex linked, int weight) {this.linked = linked;this.weight = weight;}
}

可以处理负边但是不能处理负环

4+-2+2+-1=3 所以没有负环

public class FloydWarshall {public static void main(String[] args) {Vertex v1 = new Vertex("v1");Vertex v2 = new Vertex("v2");Vertex v3 = new Vertex("v3");Vertex v4 = new Vertex("v4");v1.edges = List.of(new Edge(v3, -2));v2.edges = List.of(new Edge(v1, 4), new Edge(v3, 3));v3.edges = List.of(new Edge(v4, 2));v4.edges = List.of(new Edge(v2, -1));List<Vertex> graph = List.of(v1, v2, v3, v4);/*k=0直接连通v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   3   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0看上面那副图的权重k=1 借助v1到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0k=2 借助v2到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  3   -1  1   0k=3 借助v3到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  0v2  4   0   2   4v3  ∞   ∞   0   2v4  3   -1  1   0k=4 借助v4到达其它顶点v1  v2  v3  v4v1  0   -1   -2  0v2  4   0   2   4v3  5   1   0   2v4  3   -1  1   0*/floydWarshall(graph);}static void floydWarshall(List<Vertex> graph) {int size = graph.size();//顶点个数int[][] dist = new int[size][size];Vertex[][] prev = new Vertex[size][size];//从哪里来// 1）初始化for (int i = 0; i < size; i++) {Vertex v = graph.get(i); // v1 (v3)内层循环顶点Map<Vertex, Integer> map = v.edges.stream().collect(Collectors.toMap(e -> e.linked, e -> e.weight));for (int j = 0; j < size; j++) {Vertex u = graph.get(j); // v3  外层循环顶点if (v == u) {dist[i][j] = 0;//相同顶点} else {dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);prev[i][j] = map.get(u) != null ? v : null;//更新上一个顶点}}}print(prev);// 2）看能否借路到达其它顶点/*v2->v1          v1->v?dist[1][0]   +   dist[0][0]dist[1][0]   +   dist[0][1]dist[1][0]   +   dist[0][2]dist[1][0]   +   dist[0][3]*/for (int k = 0; k < size; k++) {for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {
//                    dist[i][k]   +   dist[k][j] // i行的顶点，借助k顶点，到达j列顶点
//                    dist[i][j]                  // i行顶点，直接到达j列顶点if (dist[i][k] != Integer.MAX_VALUE &&dist[k][j] != Integer.MAX_VALUE &&dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];prev[i][j] = prev[k][j];}}}
//            print(dist);}print(prev);for(int i=0;i<size;i++){for(int j=0;j<size;j++){path(prev,graph,i,j);}}}static void path(Vertex[][] prev, List<Vertex> graph, int i, int j) {LinkedList<String> stack = new LinkedList<>();System.out.print("[" + graph.get(i).name + "," + graph.get(j).name + "] ");stack.push(graph.get(j).name);while (i != j) {Vertex p = prev[i][j];stack.push(p.name);j = graph.indexOf(p);}System.out.println(stack);}static void print(int[][] dist) {System.out.println("-------------");for (int[] row : dist) {System.out.println(Arrays.stream(row).boxed().map(x -> x == Integer.MAX_VALUE ? "∞" : String.valueOf(x)).map(s -> String.format("%2s", s)).collect(Collectors.joining(",", "[", "]")));}}static void print(Vertex[][] prev) {System.out.println("-------------------------");for (Vertex[] row : prev) {System.out.println(Arrays.stream(row).map(v -> v == null ? "null" : v.name).map(s -> String.format("%5s", s)).collect(Collectors.joining(",", "[", "]")));}}}

Floyd能否判断负环