floydspall.java

个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF遍历,

package twf.weightedgraph.shortestpath;

import twf.weightedgraph.Edge;
import twf.weightedgraph.Graph;
import twf.weightedgraph.Path;

public class FloydSPall {
    private Edge[][] p;
    private double[][] d;
    public FloydSPall (Graph G) {
    	int V = G.V();
    	double maxWT = V;
        p = new Edge[V][V]; d = new double[V][V];
        for (int s = 0; s < V; s++)
          for (int t = 0; t < V; t++)
            d[s][t] = maxWT;
        for (int s = 0; s < V; s++)
          for (int t = 0; t < V; t++)
            if (G.edge(s, t) != null)
              { p[s][t] = G.edge(s, t);
                d[s][t] = G.edge(s, t).wt(); }
        for (int s = 0; s < V; s++) d[s][s] = 0.0;
        for (int i = 0; i < V; i++)
          for (int s = 0; s < V; s++)
            if (p[s][i] != null)
              for (int t = 0; t < V; t++)
                if (s != t)
                 if (d[s][t] > d[s][i] + d[i][t])
                   { p[s][t] = p[s][i];
                     d[s][t] = d[s][i] + d[i][t]; }

    }
    public double dist(int s, int t) {
    	return d[s][t];
    }
    public Edge pathR(int s, int t) {
    	return p[s][t];
    }
    public Path path(int s, int t) {
        Edge e =p[s][t];
        if (e == null) return null;
        Path path = new Path(e, null);
        while (t != s) {
        	t = e.other(t);
        	e = p[s][t];
        	path = new Path(e, path);
        }
        return path;
    }
}