Dijkstra算法
在為了尋找加權(quán)無向圖中的最小生成樹的Prim算法中沾鳄，構(gòu)造最小生成樹的每一步都向這棵樹中添加一條新的邊虏辫。Dijkstra算法采用了類似的方法來計算最短路徑樹。首先將distTo[s]初始化為0硼补，distTo[]中的其他元素初始化為無窮大利花。然后將distTo[]最小的非樹頂點(diǎn)松弛并加入樹中微酬，直到所有的頂點(diǎn)都在樹中或所有的非樹頂點(diǎn)distTo[]都為無窮大。
在一幅含有v個頂點(diǎn)和e條邊的加權(quán)有向圖中橄务，使用Dijkstra算法計算根結(jié)點(diǎn)為給定的最短路徑樹所需的空間與v成正比幔托，時間與elogv成正比（最壞情況下）。
最短路徑的Dijkstra算法
public class Dijikstra{
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Double> pq;
public DijikstraSP(EdgeWeightedDigraph G, int s){
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ<Double>(G.V());
for(int v = 0; v<G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
pq.insert(s, 0, 0);
while(!pq.isEmpty())
relax(G, pq.delMin());
}
private void relax(EdgeWeightedDigraph G, int v){
for(DirectedEdge e:G.adj(v)){
int w = e.to();
if(distTo[w] > distTo[v] + e.weighted()){
distTo[w] = distTo[v] + e.weighted();
edgeTo[w] = e;
if(pq.contains(w)) pq.change(w, distTo[w]);
else pq.insert(w,distTo[w]);
}
}
}
public double distTo(int v)
public boolean hasPathTo(int v)
public Iterable<DirectedEdge> pathTo(int v)
}
無環(huán)加權(quán)有向圖中的最短路徑算法
許多應(yīng)用中的加權(quán)有向圖中都是不含有環(huán)的蜂挪。本算法比Dijkstra算法更快重挑，更簡單的在無環(huán)加權(quán)有向圖中找出最短路徑迫肖，它的特點(diǎn)是：
- 能在線性時間內(nèi)解決單點(diǎn)最短路徑問題
- 能夠處理負(fù)權(quán)重的邊
- 能夠解決相關(guān)的問題，例如找出最長的路徑
將拓?fù)渑判蚺c頂點(diǎn)的放松結(jié)合起來攒驰，就可以得到該算法蟆湖。首先將distTo[0]初始化為0，其他distTo[]元素初始化為無窮大玻粪，然后一次按照拓?fù)渑判虻捻樞蛩沙谒许旤c(diǎn)隅津。
public class AcyclicSP{
private DirectedEdge[] edgeTo;
private double[] distTo;
public AcyclicSP(EdgeWeightedDigraph G, int s){
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
for ( int v=0; v<G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0;
Topological top = new Topological(G);
for( int v:top.order())
relax(G,v);
}
private void relax(EdgeWeightedDigraph G,int v)
public double distTo(int v)
public boolean hasPathTo(int v)
public Iterable<DirectedEdge> pathTo(int v)
算法應(yīng)用
優(yōu)先級限制下的并行任務(wù)調(diào)度問題。 給定一組需要完成的任務(wù)和每個任務(wù)需要的時間劲室，以及一組關(guān)于任務(wù)完成的先后次序的優(yōu)先級限制伦仍。在滿足限制條件的前提下如何在若干相同的處理器上安排任務(wù)并在最短時間內(nèi)完成任務(wù)。
解決并行任務(wù)調(diào)度問題的關(guān)鍵路徑方法步驟如下：創(chuàng)建一幅無環(huán)加權(quán)有向圖很洋，其中包含一個起點(diǎn)s和一個終點(diǎn)t且每個任務(wù)都對應(yīng)著兩個頂點(diǎn)（一個起始頂點(diǎn)和一個終止頂點(diǎn)）充蓝。對于每個任務(wù)都有一條從它的起始頂點(diǎn)到終止頂點(diǎn)的邊，邊的權(quán)重即為任務(wù)所需要的時間喉磁。對于每條優(yōu)先級限制v->w谓苟，添加一條從v的結(jié)束頂點(diǎn)指向w的起始頂點(diǎn)權(quán)重為0的邊。我們還需要為每個任務(wù)添加一條從起點(diǎn)指向該任務(wù)的起始頂點(diǎn)的權(quán)重為0的邊以及一條從該任務(wù)的終止頂點(diǎn)指向到終點(diǎn)的權(quán)重為0的邊协怒。這樣每個任務(wù)預(yù)計開始的時間即為從起點(diǎn)到它的起始頂點(diǎn)的最長距離涝焙。
public class CPM{
public static void main(String[] args){
int N = StdIn.readInt(); StdIn.readLine();
EdgeWeightedDigraph G;
G = new EdgeWeightedDigraph(2*N+2);
int s = 2*N, t=2*N+1;
for(int i=0; i<N; i++){
String[] a= StdIn.readLine().split("\\s+");
double duration = Double.parseDouble(a[0]);
G.addEdge(new DirectedEdge(i, i+N, duration));
G.addEdge(new DirectedEdge(s,i,0));
G.addEdge(new DirectedEdge(i+N,t,0)
for(int j=1; j<a.length;j++){
int successor = Integer.parseInt(a[j]);
G.addEdge(new DirectedEdge(i+N, successor, 0));
}
}
AcyclicLP lp = new AcyclicLP(G, s);
StdOut.println("Start times:");
for(int i=0;i<N; i++)
StdOut.printf("%4d: %5.1f\n",i, lp.distTo(i));
StdOut.printf("Finsh time:%5.1f\n",lp.distTo(t));
}
}