【算法基础实验】图论-Dijkstra最短路径

理论知识

边的放松

在这里插入图片描述

边的放松（Edge Relaxation）是图算法中的一个关键操作，主要用于解决最短路径问题。它的核心思想是在遍历图的过程中，通过比较和更新路径的长度，逐步找到从起点到每个顶点的最短路径。

边的放松过程

假设我们有一个从顶点 v 到顶点 w 的边 e，其权重为 weight(v, w)。边的放松操作如下：

检查当前路径：检查通过 v 到达 w 的路径是否比已经记录的从起点到 w 的路径更短。
更新路径：如果通过 v 到达 w 的路径更短，则更新 w 的最短路径长度，并将 w 的前驱顶点设置为 v。

数学表达式为：

$d i s tT o [w] > d i s tT o [v] + w e i g h t (v, w)$

THEN

$d i s tT o [w] = d i s tT o [v] + w e i g h t (v, w)$

$e d g e T o [w] = e$

其中：

distTo[w] 表示从起点到 w 的当前已知最短路径长度。
distTo[v] + weight(v, w) 表示通过 v 到达 w 的路径长度。
edgeTo[w] 表示当前最短路径中 w 的前驱节点。

已知树结点所对应的 distTo[] 值均为最短路径的长度。对于优先队列中的任意顶点 w，distTo[w]是从 s 到 w 的最短路径的长度，该路径上的中间顶点在树中且路径结束于横切边edgeTo[w]。优先级最小的顶点的 distTo[] 值就是最短路径的权重，它不会小于已经被放松过的任意顶点的最短路径的权重，也不会大于还未被放松过的任意顶点的最短路径的权重。这个顶点就是下一个要被放松的顶点。所有从 s 可达的顶点都会按照最短路径的权重顺序被放松。
在这里插入图片描述

实验数据

算法轨迹

是算法处理样图 tinyEWD.txt 时的轨迹。在这个例子中，算法构造最短路径
树的过程如下所述。
将顶点 0 添加到树中，将顶点 2 和 4 加入优先队列。
从优先队列中删除顶点 2，将 0 → 2 添加到树中，将顶点 7 加入优先队列。
从优先队列中删除顶点 4，将 0 → 4 添加到树中，将顶点 5 加入优先队列，边
4 → 7 失效。
从优先队列中删除顶点 7，将 2 → 7 添加到树中，将顶点 3 加入优先队列，边
7 → 5 失效。
从优先队列中删除顶点 5，将 4 → 5 添加到树中，将顶点 1 加入优先队列，边
5 → 7 失效。
从优先队列中删除顶点 3，将 7 → 3 添加到树中，将顶点 6 加入优先队列。
从优先队列中删除顶点 1，将 5 → 1 添加到树中，边 1 → 3 失效。
从优先队列中删除顶点 6，将 3 → 6 添加到树中。
在这里插入图片描述

代码实现

java">import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myDijkstraSP {private myDirectedEdge[] edgeTo;private double[] distTo;private myIndexMinPQ<Double> pq;public myDijkstraSP(myEdgeWeightedDigraph G, int s){edgeTo = new myDirectedEdge[G.V()];distTo = new double[G.V()];pq = new myIndexMinPQ<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(myEdgeWeightedDigraph G, int v){for(myDirectedEdge e:G.adj(v)){int w = e.to();if(distTo[w] > distTo[v] + e.weight()){distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;if(pq.contains(w)) pq.change(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<myDirectedEdge> pathTo(int v){if(!hasPathTo(v)) { return null; }myLInkedStack<myDirectedEdge> path = new myLInkedStack<myDirectedEdge>();for(myDirectedEdge e = edgeTo[v];e!=null;e = edgeTo[e.from()])path.push(e);return path;}public static void main(String[] args){myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(new In(args[0]));int s = Integer.parseInt(args[1]);myDijkstraSP sp = new myDijkstraSP(G,s);for(int i = 0; i<G.V(); i++){StdOut.print(s + " to " + i);StdOut.printf(" (%.2f): ",sp.distTo(i));if(sp.hasPathTo(i))for(myDirectedEdge e:sp.pathTo(i))StdOut.print(e + "  ");StdOut.println();}}
}

代码详解

这段代码实现了 Dijkstra 最短路径算法，用于计算加权有向图中从给定起点到所有其他顶点的最短路径。Dijkstra 算法是一种广泛应用的图算法，特别适用于边权重非负的图。下面我们将详细讲解代码的各个部分。

类变量和构造函数

java">private myDirectedEdge[] edgeTo;  // 存储从起点到每个顶点的最短路径上的最后一条边
private double[] distTo;          // 存储从起点到每个顶点的最短路径长度
private myIndexMinPQ<Double> pq;  // 索引优先队列，用于动态找到具有最小distTo值的顶点public myDijkstraSP(myEdgeWeightedDigraph G, int s) {edgeTo = new myDirectedEdge[G.V()];distTo = new double[G.V()];pq = new myIndexMinPQ<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());
}

edgeTo：存储到达每个顶点的最短路径的最后一条边，用于在构建路径时回溯。
distTo：存储从起点 s 到每个顶点的最短路径长度。初始化为正无穷大（表示未知路径），起点 s 的距离设置为 0.0。
pq：索引优先队列，用于在算法执行过程中动态获取当前距离最短的顶点。
构造函数：初始化 edgeTo 和 distTo 数组，设置起点 s 的初始距离，并将 s 插入优先队列，然后开始循环放松（relax）过程，逐步确定最短路径。
relax 方法

java">private void relax(myEdgeWeightedDigraph G, int v) {for (myDirectedEdge e : G.adj(v)) {int w = e.to();if (distTo[w] > distTo[v] + e.weight()) {distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;if (pq.contains(w)) pq.change(w, distTo[w]);else pq.insert(w, distTo[w]);}}
}

功能：relax 方法用于“放松”从顶点 v 出发的所有边。对于每条边 e（从 v 到 w），如果通过 v 到达 w 的路径比当前已知的最短路径更短，则更新 distTo[w] 和 edgeTo[w]，并更新优先队列 pq。
放松操作：如果通过 v 到达 w 的路径更短（即 distTo[v] + e.weight() 小于 distTo[w]），就更新 distTo[w] 和 edgeTo[w]，并调整优先队列中的位置。
其他方法

java">public double distTo(int v) { return distTo[v]; }public boolean hasPathTo(int v) { return distTo[v] < Double.POSITIVE_INFINITY; }public Iterable<myDirectedEdge> pathTo(int v) {if (!hasPathTo(v)) { return null; }myLInkedStack<myDirectedEdge> path = new myLInkedStack<myDirectedEdge>();for (myDirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])path.push(e);return path;
}

distTo(int v)：返回从起点 s 到顶点 v 的最短路径长度。
hasPathTo(int v)：检查从起点 s 到顶点 v 是否存在路径（即 distTo[v] 是否为正无穷大）。
pathTo(int v)：返回从起点 s 到顶点 v 的最短路径。通过回溯 edgeTo 数组构建路径。
main 方法

java">public static void main(String[] args) {myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(new In(args[0]));int s = Integer.parseInt(args[1]);myDijkstraSP sp = new myDijkstraSP(G, s);for (int i = 0; i < G.V(); i++) {StdOut.print(s + " to " + i);StdOut.printf(" (%.2f): ", sp.distTo(i));if (sp.hasPathTo(i))for (myDirectedEdge e : sp.pathTo(i))StdOut.print(e + "  ");StdOut.println();}
}

main 方法：从文件读取有向加权图 G，然后调用 myDijkstraSP 类计算从给定起点 s 出发的最短路径。
打印结果：对于每个顶点 i，打印从起点 s 到 i 的最短路径和路径长度。如果路径存在，则按顺序打印路径上的每条边。
总结
这段代码实现了 Dijkstra 最短路径算法。通过优先队列 myIndexMinPQ，代码能够高效地找到当前最短路径，并通过 relax 操作不断优化和更新路径信息。最终，算法能够求得从给定起点到图中所有其他顶点的最短路径，并通过 pathTo 方法返回最短路径的具体边。

实验步骤

java">
C:\Users\xyz\IdeaProjects\algrithoms\src>javac myDijkstraSP.java C:\Users\xyz\IdeaProjects\algrithoms\src>java myDijkstraSP data\tinyEWD.txt 0
0 to 0 (0.00): 
0 to 1 (1.05): 0 -> 4 0.38  4 -> 5 0.35  5 -> 1 0.32
0 to 2 (0.26): 0 -> 2 0.26
0 to 3 (0.99): 0 -> 2 0.26  2 -> 7 0.34  7 -> 3 0.39
0 to 4 (0.38): 0 -> 4 0.38
0 to 5 (0.73): 0 -> 4 0.38  4 -> 5 0.35
0 to 6 (1.51): 0 -> 2 0.26  2 -> 7 0.34  7 -> 3 0.39  3 -> 6 0.52
0 to 7 (0.60): 0 -> 2 0.26  2 -> 7 0.34

辅助方法

myDirectedEdge

java">public class myDirectedEdge {private int v;private int w;private final double weight;public myDirectedEdge(int v, int w, double weight){this.v = v;this.w = w;this.weight = weight;}public double weight(){ return weight; }public int from(){ return v; }public int to(){ return w; }public String toString(){ return String.format("%d -> %d %.2f",v,w,weight); }
}

myEdgeWeightedDigraph

java">import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myEdgeWeightedDigraph {private myBag<myDirectedEdge>[] adj;private int V;private int E;private static final String NEWLINE = System.getProperty("line.separator");public myEdgeWeightedDigraph(int V){this.V = V;this.E = 0;adj = (myBag<myDirectedEdge>[]) new myBag[V];for(int v=0;v<V;v++)adj[v] = new myBag<myDirectedEdge>();}public myEdgeWeightedDigraph(In in){this(in.readInt());int E = in.readInt();for(int i = 0; i<E; i++){int v = in.readInt();int w = in.readInt();double weight = in.readDouble();myDirectedEdge e = new myDirectedEdge(v,w,weight);addEdge(e);}}public void addEdge(myDirectedEdge e){adj[e.from()].add(e);E++;}public int V() {return V;}public int E() {return E;}public Iterable<myDirectedEdge> adj(int v) { return adj[v]; }public Iterable<myDirectedEdge> edges(){myBag<myDirectedEdge> bag = new myBag<myDirectedEdge>();for(int v = 0;v<V;v++)for(myDirectedEdge e:adj[v])bag.add(e);return bag;}public String toString() {StringBuilder s = new StringBuilder();s.append(V + " vertexes " + E + " edges " + NEWLINE);for (int v = 0; v < V; v++) {s.append(v + ": ");for (myDirectedEdge e : adj[v]) {s.append(e + "  ");}s.append(NEWLINE);}return s.toString();}public static void main(String[] args){In in = new In(args[0]);myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(in);StdOut.println(G);}
}