文章目录
- 1 最短路径
- 2 最短路径的性质
- 3 加权有向图的数据结构
- 3.1 加权有向边
- 3.2 加权有向图
- 4 最短路径
- 4.1 最短路径API
- 4.2 最短路径的数据结构
- 4.3 边的松弛
- 4.4 顶点的松弛
- 结语
1 最短路径
如图1-1所示,一幅加权有向图和其中的一条最短路径:
定义:在一幅加权有向图中,从顶点t到顶点s的最短路径是所有从s到t的路径中权重最小者。
**单点最短路径。**给定一幅加权有向图和一个起点s,回答“从s到给定目的顶点v是否存在一条有向路径?如果有,找出最短(总权重最小)的那条路径。“等类似问题。
2 最短路径的性质
最短路径问题的基本定义很简单,但是有些问题需要我们解决:
- **路径上有向的。**最短路径需要考虑到各条边的方向。
- **权重不一定等价于距离。**权重可以表示时间、花费等,也不一定 和距离的远近成正比。
- **并不是所有顶点都是可达的。**如果t并不是从s可达的,那么就不存在任何路径,也就不存在从s到t到最短路径。为了简化问题,我们的样图都是强连通的。
- **父权重会使问题更复杂。**我们暂时假设边的权重都是正的(或零),父权重在后面讨论。
- 最短路径一般都是简单的。我们的算法会忽略构成环的零权重边,因此找到的最短路径都不会含有环。
- **最短路径不一定是唯一的。**从一个顶点到达另一个顶点的权重最小的路径可能有多条,我们只要找到其中一条即可。
- **可能存在平行边或自环。**平行边中的权重最小者才会被选中,最短路径也不可能包含自环(除非自环的权重为零,但我们会忽略它)。为零避免歧义我们隐式地假设平行边不存在,用v->w表示从v到w到边。
我们的重点是单点最短路径问题,其中给出起点s,计算的结果是一棵最短路径树(SPT),它包含了顶点s到所有可达到顶点的最短路径。如图2-1所示:
给定一幅加权有向图和一个顶点s,以s为起点的一颗最短路径树树图的一幅子图,它包含s和从s可达的所有顶点。这颗有向树的根结点为s,树中的每条路径都是有向图中的一条最短路径。
3 加权有向图的数据结构
3.1 加权有向边
有向边的数据结构比无向边简单,因为有向边只有一个方向,这里定义了from()和to()方法,API如下表3.1-1所示:
public class | DirectedEdge | |
---|---|---|
public | DirectedEdge(int v, int w, double weight) | |
public double | weight() | 边的权重 |
public int | from() | 指出这条边的顶点 |
public int | to() | 这条边指向的顶点 |
public String | toString() | 对象的字符串表示 |
有向边DirectedEdge源代码3.1-1如下所示:
package edu.princeton.cs.algs4;
/*** 有向边*/public class DirectedEdge { /*** 边的起点*/private final int v;/*** 边的终点*/ private final int w;/*** 边的权重*/ private final double weight;/*** 初始化权重weight,从顶点v指向w的有向边* @param v 边的起点* @param w 边的终点* @param weight 边的权重*/public DirectedEdge(int v, int w, double weight) {if (v < 0) throw new IllegalArgumentException("Vertex names must be non-negative integers");if (w < 0) throw new IllegalArgumentException("Vertex names must be non-negative integers");if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");this.v = v;this.w = w;this.weight = weight;}/*** 返回边的起点* @return 边的起点*/public int from() {return v;}/*** 边的终点* @return 边的终点*/public int to() {return w;}/*** 边的权重* @return 边的权重 */public double weight() {return weight;}/*** 边的字符串表示* @return 边的字符串表示*/public String toString() {return v + "->" + w + " " + String.format("%5.2f", weight);}
}
3.2 加权有向图
加权有向图API如下表3.2-1所示:
public class | EdgeWeightedDigraph | |
---|---|---|
public | EdgeWeightedDigraph(int V) | 初始化含有V个顶点的空有向图 |
public | EdgeWeightedDigraph(In in) | 从输入流读取取构造加权有向图 |
public int | V() | 顶点总是 |
public int | E() | 边的总数 |
public void | addEdge(DirectedEdge e) | 添加一条有向边 |
public Iterable<DirectedEdge> | adj(int v) | 从v指出的边 |
public Iterable<DirectedEdge> | eges() | 该有向图的所有边 |
public String | toString | 加权有向图的字符串表示 |
加权有向图EdgeWeightedDigraph 源代码3.2-1如下所示:
package edu.princeton.cs.algs4;import java.util.NoSuchElementException;/*** 加权有向图*/
public class EdgeWeightedDigraph {private static final String NEWLINE = System.getProperty("line.separator");/*** 顶点总数*/ private final int V;/*** 边的总数*/ private int E;/*** 顶点指出的边*/ private Bag<DirectedEdge>[] adj;/*** 入度*/ private int[] indegree;/*** 初始化V个顶点的空有向图** @param V 顶点数*/public EdgeWeightedDigraph(int V) {if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be non-negative");this.V = V;this.E = 0;this.indegree = new int[V];adj = (Bag<DirectedEdge>[]) new Bag[V];for (int v = 0; v < V; v++)adj[v] = new Bag<DirectedEdge>();}/*** 初始化v个顶点e条边的加权有向图** @param 顶点总是* @param 边的总数*/public EdgeWeightedDigraph(int V, int E) {this(V);if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be non-negative");for (int i = 0; i < E; i++) {int v = StdRandom.uniform(V);int w = StdRandom.uniform(V);double weight = 0.01 * StdRandom.uniform(100);DirectedEdge e = new DirectedEdge(v, w, weight);addEdge(e);}}/** * 从输入流读取数据初始化加权有向图** @param 输入流*/public EdgeWeightedDigraph(In in) {if (in == null) throw new IllegalArgumentException("argument is null");try {this.V = in.readInt();if (V < 0) throw new IllegalArgumentException("number of vertices in a Digraph must be non-negative");indegree = new int[V];adj = (Bag<DirectedEdge>[]) new Bag[V];for (int v = 0; v < V; v++) {adj[v] = new Bag<DirectedEdge>();}int E = in.readInt();if (E < 0) throw new IllegalArgumentException("Number of edges must be non-negative");for (int i = 0; i < E; i++) {int v = in.readInt();int w = in.readInt();validateVertex(v);validateVertex(w);double weight = in.readDouble();addEdge(new DirectedEdge(v, w, weight));}} catch (NoSuchElementException e) {throw new IllegalArgumentException("invalid input format in EdgeWeightedDigraph constructor", e);}}/*** 用一个加权有向图初始化加权有向图** @param 加权有向图G*/public EdgeWeightedDigraph(EdgeWeightedDigraph G) {this(G.V());this.E = G.E();for (int v = 0; v < G.V(); v++)this.indegree[v] = G.indegree(v);for (int v = 0; v < G.V(); v++) {// reverse so that adjacency list is in same order as originalStack<DirectedEdge> reverse = new Stack<DirectedEdge>();for (DirectedEdge e : G.adj[v]) {reverse.push(e);}for (DirectedEdge e : reverse) {adj[v].add(e);}}}/*** 顶点总数** @return 顶点总是*/public int V() {return V;}/*** 边的总数** @return 边的总数*/public int E() {return E;}/*** 校验顶点v*/private void validateVertex(int v) {if (v < 0 || v >= V)throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));}/*** 添加一条有向边e** @param e 有向边e*/public void addEdge(DirectedEdge e) {int v = e.from();int w = e.to();validateVertex(v);validateVertex(w);adj[v].add(e);indegree[w]++;E++;}/*** 顶点v的指出边** @param v 顶点v* @return 顶点v指出的边*/public Iterable<DirectedEdge> adj(int v) {validateVertex(v);return adj[v];}/*** 顶点v的出度** @param v 顶点v* @return 顶点v的出度*/public int outdegree(int v) {validateVertex(v);return adj[v].size();}/*** 顶点v的入度** @param v 顶点v* @return 顶点v的入度*/public int indegree(int v) {validateVertex(v);return indegree[v];}/*** 所有边** @return 所有边*/public Iterable<DirectedEdge> edges() {Bag<DirectedEdge> list = new Bag<DirectedEdge>();for (int v = 0; v < V; v++) {for (DirectedEdge e : adj(v)) {list.add(e);}}return list;} /*** 加权有向图的字符串表示* @return 加权有向图的字符串表示*/public String toString() {StringBuilder s = new StringBuilder();s.append(V + " " + E + NEWLINE);for (int v = 0; v < V; v++) {s.append(v + ": ");for (DirectedEdge e : adj[v]) {s.append(e + " ");}s.append(NEWLINE);}return s.toString();}
}
加权有向图示意图3.2-1如下所示:
4 最短路径
4.1 最短路径API
public class | SP | |
---|---|---|
public | SP(EdgeWeightedDigraph G, int s) | 构造函数 |
public double | distTo(int v) | 从顶点s到顶点v的距离,不存在路径为无穷大 |
public boolean | hasPathTo(int v) | 是否存在从顶点s到v的路径 |
public Iterable<DirectedEdge> | pathTo(int v) | 从顶点s到v的路径,不存在为null |
4.2 最短路径的数据结构
表示最短路径 所需的数据结构很简单,如下图4.2-1所示:
- 最短路径树中的边。使用一个由顶点索引的DirectedEdge对象的父链接数组edgeTo[],其中edgeTo[v]的值为连接v和它的父结点的边。
- 到达起点的距离。由顶点索引的distTo[],其中distTo[v]表示从起点s到v的已知最短路径的长度。
我们约定edgeTo[s]为null,distTo[s]值为0。同时约定,从起点到不可达到顶点的距离均为Double.POSITIVE_INFINITY。
4.3 边的松弛
我们的最短路径API的实现都基于一个被称为松弛的操作。
-
边的松弛。放松边v->w意味着检查从s到w到最短路径是否是先从s到v,然后在由v到w。如果是,则根据这个情况更新数据结构的内容。由v到w到最短路径是distTo[v]与e.weight()之和-如果这个值小于distTo[w],称这条边失效了并将它忽略;如果这个值更新,就更新数据。代码实现4.3-1如下所示:
private void relax(DirectedEdge e) {int v = e.from(), w = e.to();if (distTo[w] > distTo[v] + e.weight()) {distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;}}
如下图4.3-1所示:
显示的是边的放松操作之后可能出现的两种情况。一种情况边失效(做边的例子),不更新任何数据;另外一种情况是v->w到达w的最短路径(右边的例子),这将会更新edgeTo[w]和distTo[w]。
4.4 顶点的松弛
实际上,实现会放松从一个顶点这出的所有边。从任意distTo[v]为有限值的顶点v指向任意distTo[]为无穷的顶点的边都是有效的。如果v被放松,那么这些有效边都会被添加到edgeTo[]中。某条从起点指出的边将会是第一天被加入edgeTo[]中的边。算法会谨慎选择起点,使得每次顶点松弛操作都能得出到达某个顶点的更短路径,最好逐渐找出到达某个顶点的最短路径。
顶点松弛代码4.4-1如下所示:
private void relax(EdgeWeightedDigraph G, int) {for(DirectedEdge e: G.adj(v)) {int w = e.to();if(distTo[w] > distTo[v]+ e.weight) {distTo[w] = distTo[v] + e.weight;edgeTo[w] = e;}}
}
结语
如果小伙伴什么问题或者指教,欢迎交流。
❓QQ:806797785
⭐️源代码仓库地址:https://gitee.com/gaogzhen/algorithm
参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法:第4版[M].北京:人民邮电出版社,2012.10.p412-419.