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