19、加权有向图
19.1、边的表示
- API
- 代码
package chapter19;
/**
* @author 土味儿
* Date 2021/9/17
* @version 1.0
* 有向边
*/
public class DirectedEdge {
/**
* 起点
*/
private final int v;
/**
* 终点
*/
private final int w;
/**
* 权重
*/
private final double weight;
/**
* 构造器
* @param v
* @param w
* @param weight
*/
public DirectedEdge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
/**
* 得到起点
* @return
*/
public int from(){
return v;
}
/**
* 得到终点
* @return
*/
public int to(){
return w;
}
/**
* 得到权重
* @return
*/
public double getWeight(){
return weight;
}
}
19.2、加权有向图的实现
- API
- 代码
package chapter19;
import chapter03.Queue;
import chapter17.Edge;
/**
* @author 土味儿
* Date 2021/9/16
* @version 1.0
* 加权有向图
*/
public class EdgeWeightedDigraph {
/**
* 顶点数量
*/
private final int vNum;
/**
* 边数量
*/
private int eNum;
/**
* 邻接表
*/
private Queue<DirectedEdge>[] adj;
/**
* 构造器
*
* @param vNum
*/
public EdgeWeightedDigraph(int vNum) {
// 初始化顶点数量
this.vNum = vNum;
// 初始化边数量
this.eNum = 0;
// 初始化邻接表
this.adj = new Queue[vNum];
// 初始化邻接表中的空队列
for (int i = 0; i < vNum; i++) {
this.adj[i] = new Queue<DirectedEdge>();
}
}
/**
* 得到顶点数量
*
* @return
*/
public int getVNum() {
return vNum;
}
/**
* 得到边数量
*
* @return
*/
public int getENum() {
return eNum;
}
/**
* 添加一条边v-w
*
* @param e
*/
public void addEdge(DirectedEdge e) {
// 因为是有向图，边加入到起点的邻接表中
int v = e.from();
this.adj[v].enQueue(e);
// 边数量加1
eNum++;
}
/**
* 获取顶点v指出的所有边
*
* @param v
* @return
*/
public Queue<DirectedEdge> adj(int v) {
return this.adj[v];
}
/**
* 获取加权有向图中的所有边
*
* @return
*/
public Queue<DirectedEdge> edges() {
// 创建一个队列对象，存储所有的边
Queue<DirectedEdge> allEdges = new Queue<>();
// 遍历图中的每一个顶点，找到每个顶点的邻接表，邻接表中存储了该顶点指出的每一个边
for (int v = 0; v < vNum; v++) {
// 遍历顶点v的邻接表，找到v指出的每一个边
for (DirectedEdge e : adj(v)) {
allEdges.enQueue(e);
}
}
return allEdges;
}
}
20、最短路径
20.1、定义及性质
-
定义
在一副加权有向图中，所有从顶点 s 到顶点 t 的路径中 总权重最小 的那条路径
-
性质
-
路径具有方向性
-
权重不一定等价于距离
权重可以是距离、时间、花费等内容，权重最小指的是成本最低
-
只考虑连通图
一副图中并不是所有的顶点都是可达的，如果s和t不可达，那么它们之间也就不存在最短路径，为了简化问题，这里只考虑连通图
-
最短路径不一定是唯一的
从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，这里只需要找出一条即可
-
-
最短路径树
- 给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径
20.2、最短路径树API设计
20.3、松弛技术
松弛这个词来源于生活：一条橡皮筋沿着两个顶点的某条路径紧紧展开，如果这两个顶点之间的路径不止一条，还有存在更短的路径，那么把皮筋转移到更短的路径上，皮筋就可以放松了
松弛这种简单的原理刚好可以用来计算最短路径树
在API中，需要用到两个成员变量edgeTo和distTo，分别存储边和权重。一开始给定一幅图G和顶点s，只知道图的边以及这些边的权重，其他的一无所知，此时初始化顶点s到顶点s的最短路径的总权重disto[s]=0；顶点s到其他顶点的总权重默认为无穷大，随着算法的执行，不断的使用松弛技术处理图的边和顶点，并按一定的条件更新edgeTo和distTo中的数据，最终就可以得到最短路径树
-
边的松弛
放松边 v->w 意味着检查从s到w的最短路径是否先从s到v，然后再从v到w？
如果是，则v-w这条边需要加入到最短路径树中，更新edgeTo和distTo中的内容：
edgeTo[w] = 表示v->w这条边的DirectedEdge对象
distTo[w] = distTo[v]+v->w这条边权重
如果不是，则忽略v->w这条边
-
顶点的松弛
顶点的松弛是基于边的松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕
例如：
要松弛顶点v，只需要遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。
如果把起点设置为顶点0，那么找出起点0到顶点6的最短路径0->2->7>3->6的过程如下:
20.4、Dijkstra算法实现
- 代码
package chapter20;
import chapter03.Queue;
import chapter07.IndexMinPriorityQueue;
import chapter19.DirectedEdge;
import chapter19.EdgeWeightedDigraph;
/**
* @author 土味儿
* Date 2021/9/18
* @version 1.0
* 迪杰斯特拉-最短路径算法
*/
public class DijkstraSP {
/**
* 最后一条边
* 索引代表顶点
* 值表示从顶点s到当前顶点的最短路径上的 最后一条边
*/
private DirectedEdge[] edgeTo;
/**
* 总权重
* 索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
*/
private double[] distTo;
/**
* 存放树中顶点与非树中顶点之间的有效横切边
*/
private IndexMinPriorityQueue<Double> pq;
/**
* 构造器
* 根据一副加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
* @param g
* @param s
*/
public DijkstraSP(EdgeWeightedDigraph g,int s) {
// 初始化edgeTo
this.edgeTo = new DirectedEdge[g.getVNum()];
// 初始化distTo
this.distTo = new double[g.getVNum()];
for(int i = 0;i<g.getVNum();i++){
// 默认值：正无穷大
this.distTo[i] = Double.POSITIVE_INFINITY;
}
// 初始化pq
this.pq = new IndexMinPriorityQueue<>(g.getVNum());
// 找到图g中以顶点s为起点的最短路径树
// 默认让顶点进入到最短路径树中
this.distTo[s] = 0.0;
this.pq.insert(s,0.0);
// 遍历pq
while(!this.pq.isEmpty()){
relax(g,this.pq.delMin());
}
}
/**
* 松驰加权有向图g中的顶点v
* @param g
* @param v
*/
private void relax(EdgeWeightedDigraph g,int v){
// 遍历顶点v的邻接表
for (DirectedEdge edge : g.adj(v)) {
// 获取该边的终点w
int w = edge.to();
// 通过松驰技术：判断从起点s到w的最短路径，是否要经过v：s -> v -> w
if(distTo[v] + edge.getWeight() < distTo[w]){
// 需要经过v：更新数据
// s到w的最短路径的总权重
distTo[w] = distTo[v] + edge.getWeight();
// 从s到w的最短路径的最后一条边
edgeTo[w] = edge;
// 更新pq
if(pq.contains(w)){
pq.changeItem(w, edge.getWeight());
}else{
pq.insert(w, edge.getWeight());
}
}
}
}
/**
* 获取从起点s到顶点v的最短路径的总权重
* @param v
* @return
*/
public double distTo(int v){
return distTo[v];
}
/**
* 判断从起点s到顶点v是否可达
* @param v
* @return
*/
public boolean hasPathTo(int v){
// 默认是正无穷大
return distTo[v] < Double.POSITIVE_INFINITY;
}
/**
* 从起点s到顶点v的最短路径的所有边
* @param v
* @return
*/
public Queue<DirectedEdge> pathTo(int v){
// 如果从起点s到v不可达，返回null
if(!hasPathTo(v)){
return null;
}
// 创建队列，接收最短路径
Queue<DirectedEdge> allEdges = new Queue<>();
// 从v开始，利用edgeTo最后边，循环反推至起点s，存入队列
while (true){
// 最小路径的最后一条边
DirectedEdge e = edgeTo[v];
// 起点的最后边为null，退出循环
if(e == null){
break;
}
// 加入队列
allEdges.enQueue(e);
// 更新v，继续循环：因为是有向边，向上反推，v等于边的起点
v = e.from();
}
return allEdges;
}
}
- 测试
package chapter20;
import chapter03.Queue;
import chapter19.DirectedEdge;
import chapter19.EdgeWeightedDigraph;
import org.junit.Test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @author 土味儿
* Date 2021/9/18
* @version 1.0
* 测试加权有向图最短路径算法
*/
public class DijkstraSPTest {
@Test
public void test() throws IOException {
// ---------准备一幅加权有向图----------
BufferedReader br = new BufferedReader(new InputStreamReader(DijkstraSPTest.class.getClassLoader().getResourceAsStream("min_route_test.txt")));
// 顶点数量
int total = Integer.parseInt(br.readLine());
// 加权有向图
EdgeWeightedDigraph g = new EdgeWeightedDigraph(total);
// 边的数量
int edgeNum = Integer.parseInt(br.readLine());
// 依次读取边
for (int i = 0; i < edgeNum; i++) {
String[] s = br.readLine().split(" ");
int v = Integer.parseInt(s[0]);
int w = Integer.parseInt(s[1]);
double weight = Double.parseDouble(s[2]);
// 创建加权有向边
DirectedEdge edge = new DirectedEdge(v, w, weight);
// 向图中加入边
g.addEdge(edge);
}
// -----创建DijkstraSP对象，查找最短路径树-----
DijkstraSP sp = new DijkstraSP(g, 0);
// 查找最短路径
Queue<DirectedEdge> edges = sp.pathTo(6);
// 打印
for (DirectedEdge e : edges) {
int v = e.from();
int w = e.to();
double weight = e.getWeight();
System.out.println(v + " - " + w + " : " + weight);
}
}
}
- 测试数据：min_route_test.txt
8
15
4 5 0.35
5 4 0.35
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93
- 运行结果
3 - 6 : 0.52
7 - 3 : 0.39
2 - 7 : 0.34
0 - 2 : 0.26