▶ 书中第四章部分程序，包括在加上自己补充的代码，Dijkstra 算法求有向 / 无向图最短路径，以及所有顶点对之间的最短路径
● Dijkstra 算法求有向图最短路径
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.IndexMinPQ; public class class01
{
private double[] distTo; // 起点到各顶点的距离
private DirectedEdge[] edgeTo; // 由于引入顶点 v 使得图中新增加的边记作 edgeTo[v]
private IndexMinPQ<Double> pq; // 搜索队列 public class01(EdgeWeightedDigraph G, int s)
{
for (DirectedEdge e : G.edges()) // 确认所有变的权值为正
{
if (e.weight() < 0)
throw new IllegalArgumentException("\n<Constructor> e.weight < 0.\n");
}
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0; // 起点
pq = new IndexMinPQ<Double>(G.V());
for (pq.insert(s, distTo[s]); !pq.isEmpty();) // 每次从搜索队列中取出一个顶点，松弛与之相连的所有边
{
int v = pq.delMin();
for (DirectedEdge e : G.adj(v))
relax(e);
}
} private void relax(DirectedEdge e)
{
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) // 加入这条边会使起点到 w 的距离变短
{
distTo[w] = distTo[v] + e.weight(); // 加入该条边，更新 w 距离
edgeTo[w] = e;
if (pq.contains(w)) // 若 w 已经在搜索队列中
pq.decreaseKey(w, distTo[w]); // 更新 w 在搜索队列中的权值为当前起点到 w 的距离
else
pq.insert(w, distTo[w]); // 否则将顶点 w 加入搜索队列
}
} public double distTo(int v)
{
return distTo[v];
} public boolean hasPathTo(int v)
{
return distTo[v] < Double.POSITIVE_INFINITY;
} public Iterable<DirectedEdge> pathTo(int v) // 生成起点到 v 的最短路径
{
if (!hasPathTo(v))
return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) // 从 v 开始不断寻找父顶点，依次压入栈中
path.push(e);
return path;
} public static void main(String[] args)
{
In in = new In(args[0]);
int s = Integer.parseInt(args[1]);
EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
class01 sp = new class01(G, s);
for (int t = 0; t < G.V(); t++)
{
if (sp.hasPathTo(t))
{
StdOut.printf("%d to %d (%.2f) ", s, t, sp.distTo(t));
for (DirectedEdge e : sp.pathTo(t))
StdOut.print(e + " ");
StdOut.println();
}
else
StdOut.printf("%d to %d no path\n", s, t);
}
}
}
● Dijkstra 算法求无向图最短路径
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.EdgeWeightedGraph;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.IndexMinPQ; public class class01
{
private double[] distTo;
private Edge[] edgeTo;
private IndexMinPQ<Double> pq; public class01(EdgeWeightedGraph G, int s)
{
for (Edge e : G.edges())
{
if (e.weight() < 0)
throw new IllegalArgumentException("\n<Constructor> e.weight < 0.\n");
}
distTo = new double[G.V()];
edgeTo = new Edge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
pq = new IndexMinPQ<Double>(G.V());
for (pq.insert(s, distTo[s]); !pq.isEmpty();)
{
int v = pq.delMin();
for (Edge e : G.adj(v))
relax(e, v);
}
} private void relax(Edge e, int v) // 无向图没有 from 和 to 分量，需要给出新边已经遍历了的那个顶点
{
int w = e.other(v);
if (distTo[w] > distTo[v] + e.weight())
{
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w))
pq.decreaseKey(w, distTo[w]);
else
pq.insert(w, distTo[w]);
}
} public double distTo(int v)
{
return distTo[v];
} public boolean hasPathTo(int v)
{
return distTo[v] < Double.POSITIVE_INFINITY;
} public Iterable<Edge> pathTo(int v)
{
if (!hasPathTo(v))
return null;
Stack<Edge> path = new Stack<Edge>();
int x = v; // 无向图需要变量记录父顶点，以便向回跳
for (Edge e = edgeTo[v]; e != null; e = edgeTo[x])
{
path.push(e);
x = e.other(x);
}
return path;
} public static void main(String[] args)
{
In in = new In(args[0]);
int s = Integer.parseInt(args[1]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
class01 sp = new class01(G, s);
for (int t = 0; t < G.V(); t++)
{
if (sp.hasPathTo(t))
{
StdOut.printf("%d to %d (%.2f) ", s, t, sp.distTo(t));
for (Edge e : sp.pathTo(t))
StdOut.print(e + " ");
StdOut.println();
}
else
StdOut.printf("%d to %d no path\n", s, t);
}
}
}
● Dijkstra 算法求所有顶点对之间的最短路径
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.DijkstraSP;
import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph; public class class01
{
private DijkstraSP[] all; public class01(EdgeWeightedDigraph G)
{
all = new DijkstraSP[G.V()];
for (int v = 0; v < G.V(); v++) // 循环，每个点为起点都来一次 DijkstraSP
all[v] = new DijkstraSP(G, v);
} public Iterable<DirectedEdge> path(int s, int t)
{
return all[s].pathTo(t);
} public boolean hasPath(int s, int t)
{
return dist(s, t) < Double.POSITIVE_INFINITY;
} public double dist(int s, int t)
{
return all[s].distTo(t);
} public static void main(String[] args)
{
In in = new In(args[0]);
EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
class01 spt = new class01(G);
StdOut.printf(" "); // 输出没对定点之间的最小路径距离
for (int v = 0; v < G.V(); v++)
StdOut.printf("%6d ", v);
StdOut.println();
for (int v = 0; v < G.V(); v++)
{
StdOut.printf("%3d: ", v);
for (int w = 0; w < G.V(); w++)
{
if (spt.hasPath(v, w)) StdOut.printf("%6.2f ", spt.dist(v, w));
else StdOut.printf(" Inf ");
}
StdOut.println();
}
StdOut.println();
for (int v = 0; v < G.V(); v++) // 输出每对顶点之间最小路径
{
for (int w = 0; w < G.V(); w++)
{
if (spt.hasPath(v, w))
{
StdOut.printf("%d to %d (%5.2f) ", v, w, spt.dist(v, w));
for (DirectedEdge e : spt.path(v, w))
StdOut.print(e + " ");
StdOut.println();
}
else
StdOut.printf("%d to %d no path\n", v, w);
}
}
}
}