dijkstragraphspt.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 48 行

package twf.weightedgraph.shortestpath;

import twf.adt.DoublePQi;
import twf.weightedgraph.AdjList;
import twf.weightedgraph.Edge;
import twf.weightedgraph.Graph;
import twf.weightedgraph.Path;

public class DijkstraGraphSPT {
	  private double[] wt;
	  private Edge[] spt;
	  private int s;
	  public DijkstraGraphSPT(Graph G, int s)
	  { this.s = s;
		int V = G.V();
	    wt = new double[V]; spt = new Edge[V];
	    double maxWT = V;
		for (int v = 0; v < V; v++) wt[v] = maxWT ;
	    DoublePQi pQ = new DoublePQi(V, wt);
	    for (int v = 0; v < V; v++) pQ.insert(v);
	    wt[s] = 0.0; pQ.lower(s);
	    while (!pQ.empty())
	    { int v = pQ.getmin(); // wt[v] = 0.0;
	      if (v != s && spt[v] == null) return;
	      AdjList A = G.getAdjList(v);
	      for (Edge e = A.beg(); !A.end(); e = A.nxt())
	        { int w = e.other(v);
	          double P = wt[v] + e.wt();
	          if (P < wt[w])
	            { wt[w] = P; pQ.lower(w); spt[w] = e; }
	        }
	      }
	   }
	   public Edge pathR(int v) { return spt[v]; }
	   public double dist(int v) { return wt[v]; }
	   public Path path(int v) {
		   Edge e;
		   if ((e = pathR(v)) == null) return null;
		   Path p = new Path(e, null);
		   while (v != s) {
			   v = e.other(v);
			   e = pathR(v);
			   p = new Path(e, p);
		   }
		   return p;
	   }
}