最小生成树

之前学习的加权图,我们发现它的边关联了一个权重,那么我们就可以根据这个权重解决最小成本问题,但是如何才能找到最小成本对应的顶点和边呢?最小生成树相关算法就可以解决

最小生成树定义及相关约定

定义:

图的生成树是它的一棵含有其所有顶点的无环连通子图,一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树

约定:

只考虑连通图,最小生成树的定义说明它只能存在于连通图中,如果图不是连通的,那么分别计算每个连通子图的最小生成树,合并到一起称为最小生成森林

所有边的权重都各不相同,如果不同的边权重可以相同,那么一幅图的最小生成树就可能不唯一了,虽然我们的算法可以处理这种情况,但是为了好理解,我们约定所有的边权重都各不相同

最小生成树原理

树的性质

  1. 用一条边连接树中的任意两个顶点都会产生一个新的环

  1. 从树中删除任意一条边,将会得到两棵独立的树

切分定理

要从一副连通图中找出该图的最小生成树,需要通过切分定理完成

切分:

将图的所有顶点按照某些规则分为两个非空且没有交集的集合

横切边:

连接两个属于不同集合的顶点的边称之为横切边,例如我们将图中的顶点切分为两个集合,灰色顶点属于一个集合,白色顶点属于另外一个集合,那么效果如下

切分定理:

在一副加权图中,给定任意的切分,它的横切边中的权重最小者必然属于图中的最小生成树

注意:一次切分产生的多个横切边中,权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边

贪心算法

贪心算法是计算图的最小生成树的基础算法,它的基本原理就是切分定理,使用切分定理找到最小生成树的一条边,不断的重复直到找到最小生成树的所有边,如果图有V个顶点,那么需要找到V-1条边,就可以表示该图的最小生成树

计算图的最小生成树的算法有很多种,但这些算法都可以看作是贪心算法的一种特殊情况,这些算法的不同之处在于保存切分和判定权重最小的横切边的方式

Prim算法

我们学习第一种计算最小生成树的方法叫Prim算法,它的每一步都会为一棵生成中的树添加一条边,一开始这棵树只有一个顶点,然后会向它添加V-1条边,每次总是将下一条连接树中的顶点与不在树种的顶点且权重最小的边加入到树中

Prim算法的切分规则:

把最小生成树中的顶点看作是一个集合,把不在最小生成树中的顶点看作是另外一个集合

Prim算法API设计

类名PrimMST
构造方法PrimMST(EdgeWeightedGraph G):根据一副加权无向图,创建最小生成树计算对象
成员方法1.private void visit(EdgeWeightedGraph G,int v):将顶点v添加到最小生成树中,并且更新数据 2.public Queue edges():获取最小生成树的所有边
成员变量1.private Edge[] edgeTo:索引代表顶点,值表示当前顶点和最小生成树之间的最短边 2.private double[] distTo:索引代表顶点,值表示当前顶点和最小生成树之间的最短边的权重 3.private boolean[] marked:索引代表顶点,如果当前顶点已经在树中,则值为true,否则为false 4.private IndexMinPriorityQueue pq:存放树中顶点与非树种顶点之间的有效横切边

Prim算法的实现原理

Prim算法始终将图中的顶点切分成两个集合,最小生成树顶点和非最小生成树顶点,通过不断的重复做某些操作,可以逐渐将非最小生成树中的顶点加入到最小生成树中,直到所有的顶点都加入到最小生成树中

我们在设计API的时候,使用最小索引优先队列存放树中顶点与非树中顶点的有效横切边,那么它是如何表示的呢?我们可以让最小索引优先队列的索引值表示图的顶点,让最小索引优先队列的值表示从其他某个顶点到当前顶点的边的权重

初始化状态,先默认0是最小生成树中的唯一顶点,其他的顶点都不在最小生成树中,此时横切边就是顶点0的邻接表中0-2,0-4,0-6,0-7这四条边,我们只需要将索引优先队列的2,4,6,7索引处分别存储这些边的权重值就可以表示了

现在只需要从这四条横切边中找出权重最小的边,然后把对应的顶点加进来即可,所以找到0-7这条横切边的权重最小,因此把0-7这条边添加进来,此时07属于最小生成树的顶点,其他的不属于,现在顶点7的邻接表中的边也成为了横切边,这时候需要做两个操作

  1. 0-7这条边已经不是横切边了,需要让它失效

    • 只需要调用最小索引优先队列的delMin()方法即可完成
  2. 24顶点各有两条连接指向最小生成树,需要只保留一条

    • 4-7的权重小于0-4的权重,所以保留4-7,调用索引优先队列的change(4,0.37)即可
    • 0-2的权重小于2-7的权重,所以保留0-2,不需要做额外操作

我们不断重复上面的动作,就可以把所有的顶点添加到最小生成树中

代码实现

PrimMST

public class PrimMST {

  /**
   * 索引代表顶点,值表示当前顶点和最小生成树之间的最短边
   */
  private Edge[] edgeTo;
  /**
   * 索引代表顶点,值表示当前顶点和最小生成树之间的最短边的权重
   */
  private double[] distTo;
  /**
   * 索引代表顶点,如果当前顶点已经在树中,则值为true,否则为false
   */
  private boolean[] marked;
  /**
   * 存放树中顶点与非树中顶点之间的有效横切边
   */
  private IndexMinPriorityQueue<Double> pq;

  /**
   * 根据一副加权无向图,创建最小生成树计算对象
   */
  public PrimMST(EdgeWeightedGraph G) {
    //初始化edgeTo
    this.edgeTo = new Edge[G.V()];
    //初始化distTo
    this.distTo = new double[G.V()];
    for (int i = 0; i < distTo.length; i++) {
      distTo[i] = Double.POSITIVE_INFINITY;
    }
    //初始化marked
    this.marked = new boolean[G.V()];
    //初始化pq
    pq = new IndexMinPriorityQueue<Double>(G.V());
    //默认让顶点0第一个进入到树中,因为0是第一个进入,没有与其他顶点通过边相连,所以让distTo对应位置的值存储0.0
    distTo[0] = 0.0;
    pq.insert(0, 0.0);
    //遍历索引最小优先队列,拿到最小横切边对应的顶点,把该顶点加入到最小生成树中
    while (!pq.isEmpty()) {
      visit(G, pq.delMin());
    }
  }

  /**
   * 将顶点v添加到最小生成树中,并且更新数据
   */
  private void visit(EdgeWeightedGraph G, int v) {
    //把顶点v添加到最小生成树中
    marked[v] = true;
    //更新数据
    for (Edge e : G.adj(v)) {
      //获取v顶点的另外一个顶点
      int w = e.other(v);
      //判断顶点w是否在树中,如果不在树中,更新数据,如果在树中,则无需处理
      if (marked[w]) {
        continue;
      } else {
        //判断边e的权重是否小于树中已经存在的最小边的权重
        //个人理解就是,最开始是0-7,让后让连接7的所有顶点,只要比0-7小,就更新数据,从而找到了最小横切边
        if (e.weight() < distTo[w]) {
          //更新数据
          edgeTo[w] = e;
          distTo[w] = e.weight();
          //如果pq中存储了有效横切边已经包含了w顶点,则需要修正最小索引优先队列w索引相关联的权重
          if (pq.contains(w)) {
            pq.changeItem(w, e.weight());
          } else {
            //如果有效横切边不包含w顶点,则直接向最小索引优先队列中添加v-w和其权重值
            pq.insert(w, e.weight());
          }
        }
      }
    }
  }

PrimMSTTest

public static void main(String[] args) throws Exception {
    //准备一副加权无向图
    BufferedReader br = new BufferedReader(new InputStreamReader(
        PrimMSTTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));
    //创建一个PrimMSTTest对象,计算加权无向图中最小生成树
    int total = Integer.parseInt(br.readLine());
    EdgeWeightedGraph G = new EdgeWeightedGraph(total);
    int edgeNumbers = Integer.parseInt(br.readLine());
    for (int i = 0; i < edgeNumbers; i++) {
      //格式为4 5 0.35
      String line = br.readLine();
      String[] s = line.split(" ");
      int v = Integer.parseInt(s[0]);
      int w = Integer.parseInt(s[1]);
      double weight = Double.parseDouble(s[2]);
      //构建加权无向边
      Edge edge = new Edge(v, w, weight);
      G.addEdge(edge);
    }
    //获取最小生成树中的所有边
    PrimMST primMST = new PrimMST(G);
    Queue<Edge> Edges = primMST.edges();
    //打印所有边即可
    for (Edge e : Edges) {
      int v = e.either();
      int w = e.other(v);
      double weight = e.weight();
      System.out.println(v + "-" + w + "::" + weight);
    }
  }

Kruskal算法

Kruskal算法是计算一副加权无向图的最小生成树的另外一种算法,它的主要思想是按照边的权重(从小到大)处理它们,将边加入最小生成树中,加入的边不会与已经加入最小生成树的边构成环,直到树中含有V-1条边为止

Kruskal算法和Prim算法的区别:

Prim算法是一条边一条边的构成最小生成树,每一步都为一棵树添加一条边,Kruskal算法构造最小生成树的时候也是一条边一条边地构造,但它的切分规则是不一样的,它每一次寻找的边会连接一片森林中的两棵树,如果一副加权无向图由V个顶点组成,初始化情况下每个顶点都构成一棵独立的树,则V个顶点对应V棵树,组成一片森林,Kruskal算法每一次处理都会将两棵树合并为一棵树,直到森林中只剩一棵树为止

Kruskal算法API设计

类名KruskalMST
构造方法KruskalMST(EdgeWeightedGraph G):根据一副加权无向图,创建最小生成树计算对象
成员方法1.public Queue edges():获取最小生成树的所有边
成员变量1.private Queue mst:保存最小生成树的所有边 2.private UF_Tree_Weighted uf:索引代表顶点,使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一棵树中,使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并 3.private MinPriorityQueue pq:存储图中所有的边,使用最小优先队列,对边按照权重进行排序

Kruskal算法的实现原理

在设计API的时候,使用了一个MinPriorityQueue<Edge> pq存储图中所有的边,每次使用pq.delMin()取出权重最小的边,并得到该边关联的两个顶点v和w,通过uf.connect(v,w)判断v和w是否已经连通,如果连通,则证明这两个顶点在同一棵树中,那么就不能再把这条边添加到最小生成树中,因为在一棵树的任意两个顶点上添加一条边,都会形成环,而最小生成树不能有环的存在,如果不连通,则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树,并把这条边加入到mst队列中,这样如果把所有的边处理完,最终mst中存储的就是最小生成树的所有边

代码实现

KruskalMST

public class KruskalMST {

  /**
   * 保存最小生成树的所有边
   */
  private Queue<Edge> mst;
  /**
   * 索引代表顶点,使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一棵树中,使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
   */
  private UF_Tree_Weighted uf;
  /**
   * 存储图中所有的边,使用最小优先队列,对边按照权重进行排列
   */
  private MinPriorityQueue<Edge> pq;

  /**
   * 根据一副加权无向图,创建最小生成树计算对象
   */
  public KruskalMST(EdgeWeightedGraph G) {
    //初始化mst
    this.mst = new Queue<Edge>();
    //初始化uf
    this.uf = new UF_Tree_Weighted(G.V());
    //初始化pq
    this.pq = new MinPriorityQueue<>(G.E());
    //把图中所有的边存储到pq中
    for (Edge e : G.edges()) {
      pq.insert(e);
    }
    //遍历pq队列,拿到最小权重的边进行处理,因为边数永远小于顶点数-1
    while (!pq.isEmpty() && mst.size() < G.V() - 1) {
      //找到权重最小的边
      Edge e = pq.delMin();
      //找到该边的两个顶点
      int v = e.either();
      int w = e.other(v);
      //判断这两个顶点是否已经在同一个树中,如果在同一个树中,如果不在同一个树中,则将这两个顶点所属的同一棵树合并为一棵树
      if (uf.connected(v, w)) {
        continue;
      }
      uf.union(v, w);
      //让边e进入到mst队列中
      mst.enqueue(e);
    }
  }

  /**
   * 获取最小生成树的所有边
   */
  public Queue<Edge> edges() {
    return mst;
  }
}

KruskalMSTTest

public static void main(String[] args) throws Exception {
    //准备一副加权无向图
    BufferedReader br = new BufferedReader(new InputStreamReader(
        KruskalMSTTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));
    //创建一个KruskalMST对象,计算加权无向图中最小生成树
    int total = Integer.parseInt(br.readLine());
    EdgeWeightedGraph G = new EdgeWeightedGraph(total);
    int edgeNumbers = Integer.parseInt(br.readLine());
    for (int i = 0; i < edgeNumbers; i++) {
      //格式为4 5 0.35
      String line = br.readLine();
      String[] s = line.split(" ");
      int v = Integer.parseInt(s[0]);
      int w = Integer.parseInt(s[1]);
      double weight = Double.parseDouble(s[2]);
      //构建加权无向边
      Edge edge = new Edge(v, w, weight);
      G.addEdge(edge);
    }
    //获取最小生成树中的所有边
    KruskalMST kruskalMST = new KruskalMST(G);
    Queue<Edge> Edges = kruskalMST.edges();
    //打印所有边即可
    for (Edge e : Edges) {
      int v = e.either();
      int w = e.other(v);
      double weight = e.weight();
      System.out.println(v + "-" + w + "::" + weight);
    }
  }

加权有向图

之前学习的加权无向图中,边是没有方向的,并且同一条边会同时出现在该边的两个顶点的邻接表中,为了能够处理含有方向性的图的问题,我们

API设计

类名DirectedEdge
构造方法DirectedEdge(int v,int w,double weight):通过顶点v和w,以及权重weight值构造一个边对象
成员方法1.public double weight():获取边的权重值 2.pubic int from():获取有向边的起点 3.public int to():获取有向边的终点
成员变量1.private final int v:起点 2.private final int w:终点 3.private final double weight:当前边的权重

代码

public class DirectedEdge {

  /**
   * 起点
   */
  private final int v;
  /**
   * 终点
   */
  private final int w;
  /**
   * 当前边的权重
   */
  private final double weight;

  /**
   * 通过顶点v和w,以及权重weight值构造一个边对象
   */
  public DirectedEdge(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;
  }
}

加权有向图的实现

之前我们已经完成了有向图,在有向图的基础上,我们只需要把边的表示切换成DirectedEdge对象即可

API设计

类名EdgeWeightedDigraph
构造方法EdgeWeightedDigraph(int V):创建一个含有V个顶点的空加权有向图
成员方法1.public int V():获取图中顶点的数量 2.public int E():获取图中边的数量 3.public void addEdge(DirectedEdge e):向加权有向图中添加一条边e 4.public Queue adj(int v):获取由顶点v指出的所有的边 5.public Queue edges():获取加权有向图的所有边
成员变量1.private final int V:记录顶点数量 2.private int E:记录边数量 3.private Queue[] adj:邻接表

代码实现

EdgeWeightedDigraph

public class EdgeWeightedDigraph {

  /**
   * 顶点总数
   */
  private final int V;
  /**
   * 边的总数
   */
  private int E;

  /**
   * 邻接表
   */
  private Queue<DirectedEdge>[] adj;

  /**
   * 创建一个含有V个顶点的空加权有向图
   */
  public EdgeWeightedDigraph(int V) {
    //初始化顶点
    this.V = V;
    //初始化边的数量
    this.E = 0;
    //初始化邻接表
    this.adj = new Queue[V];
    for (int i = 0; i < adj.length; i++) {
      adj[i] = new Queue<DirectedEdge>();
    }
  }

  /**
   * 获取图中顶点的数量
   */
  public int V() {
    return V;
  }

  /**
   * 获取图中边的数量
   */
  public int E() {
    return E;
  }

  /**
   * 向加权有向图中添加一条边e
   */
  public void addEdge(DirectedEdge e) {
    //边e是有方向的,所以只需要让e出现在起点的邻接表即可
    int v = e.from();
    adj[v].enqueue(e);
    //边的数量+1
    E++;
  }

  /**
   * 获取由顶点v指出的所有的边
   */
  public Queue<DirectedEdge> adj(int v) {
    return adj[v];
  }

  /**
   * 获取加权有向图的所有的边
   */
  public Queue<DirectedEdge> edges() {
    //遍历图中的每一个顶点,得到该顶点的邻接表,遍历每一条边,添加到队列中即可
    Queue<DirectedEdge> allEdges = new Queue<>();
    for (int v = 0; v < V; v++) {
      for (DirectedEdge directedEdge : adj[v]) {
        allEdges.enqueue(directedEdge);
      }
    }
    return allEdges;
  }
}

最短路径

有了加权有向图之后,我们立刻就能联想到实际生活中的使用场景,例如在一副地图中,找到地点a与地点b之间的路径,这条路径可以是距离最短,也可以是时间最短,也可以是费用最小等,如果我们把距离/时间/费用看作成本,那么就需要找到地点a和地点b之间成本最小的路径,也就是我们接下来要解决的最短路径问题

最短路径定义及性质

定义:在一副加权有向图中,从顶点s到顶点t的最短路径是从顶点s到顶点t的路径中总权重最小的那条路径

性质:

  1. 路径具有方向性
  2. 权重不一定等价于距离,权重也可以是距离,时间,花费等内容,权重最小指的是成本最低
  3. 只考虑连通图,一幅图中并不是所有的顶点都是可达的,如果s和t不可达,那么它们之间也就不存在最短路径,为了简化问题,这里只考虑连通图
  4. 最短路径不一定是唯一的,从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条,这里只需要找出一条即可

最短路径树:

给定一幅加权有向图和一个顶点s,以s为起点的一棵最短路径树是图的一幅子图,它包含顶点s以及从s可达的所有顶点,这棵有向树的根节点为s,树的每条路径都是有向图中的一条最短路径

最短路径树API设计

计算最短路径树的经典算法是Dijkstra算法,为了实现它,先设计如下API

类名DijkstraSP
构造方法public DijkstraSP(EdgeWeightedDigraph G,int s):根据一副加权有向图G和顶点s,创建一个计算顶点为s的最短路径树对象
成员方法1.private void relax(EdgeWeightedDigraph G,int v):松弛图G中的顶点v 2.public double distTo(int v):获取从顶点s到顶点v的最短路径的总权重 3.public boolean hasPathTo(int v):判断从顶点s到顶点v是否可达 4.public Queue pathTo(int v):查询从起点s到顶点v的最短路径中所有的边
成员变量1.private DirectedEdge[] edgeTo:索引代表顶点,值表示从顶点s到当前顶点的最短路径上的最后一条边 2.private double[] distTo:索引代表顶点,值表示从顶点s到当前顶点的最短路径的总权重 3.private IndexMinPriorityQueue pq:存放树中顶点与非树中顶点之间的有效横切边

代码实现

DijkstraSP

public class DijkstraSP {

  /**
   * 索引代表顶点,值表示从顶点s到当前顶点的最短路径上的最后一条边
   */
  private DirectedEdge[] edgeTo;
  /**
   * 索引代表顶点,值表示从顶点s到当前顶点的最短路径的总权重
   */
  private double[] distTo;
  /**
   * 存放树中顶点与非树中顶点之间的有效横切边
   */
  private IndexMinPriorityQueue<Double> pq;

  /**
   * 根据一副加权有向图G和顶点s,创建一个计算顶点为s的最短路径树对象
   */
  public DijkstraSP(EdgeWeightedDigraph G, int s) {
    //初始化edgeTo
    this.edgeTo = new DirectedEdge[G.V()];
    //初始化distTo
    this.distTo = new double[G.V()];
    for (int i = 0; i < distTo.length; i++) {
      distTo[i] = Double.POSITIVE_INFINITY;
    }
    //初始化pq
    this.pq = new IndexMinPriorityQueue<>(G.V());
    //找到图G中以顶点s为起点的最短路径树
    //默认让顶点s进入到最短路径树中
    distTo[s] = 0.0;
    pq.insert(s, 0.0);
    //遍历pq,拿到边进行松弛
    while (!pq.isEmpty()) {
      relax(G, pq.delMin());
    }
  }

  /**
   * 松弛图G中的顶点v
   */
  private void relax(EdgeWeightedDigraph G, int v) {
    //遍历该顶点的邻接表
    for (DirectedEdge directedEdge : G.adj(v)) {
      //获取该边的终点w
      int w = directedEdge.to();
      //通过松弛技术,判断起点s到顶点w的最短路径是否需要先从顶点s到顶点v,再从顶点v到顶点w
      if (distTo(v) + directedEdge.weight() < distTo(w)) {
        //更新松弛数据
        distTo[w] = distTo[v] + directedEdge.weight();
        edgeTo[w] = directedEdge;
        //判断pq中是否已经存在顶点w,如果存在,则更新权重,如果不存在,则直接添加数据
        if (pq.contains(w)) {
          pq.changeItem(w, distTo[w]);
        } else {
          pq.insert(w, distTo[w]);
        }
      }
    }
  }

  /**
   * 获取从顶点s到顶点v的最短路径的总权重
   */
  public double distTo(int v) {
    return distTo[v];
  }

  /**
   * 判断从顶点s到顶点v是否可达
   */
  public boolean hasPathTo(int v) {
    return distTo[v] < Double.POSITIVE_INFINITY;
  }

  /**
   * 查询从起点s到顶点v的最短路径中的所有边
   */
  public Queue<DirectedEdge> pathTo(int v) {
    //判断从顶点s到顶点v是否可达
    if (!hasPathTo(v)) {
      return null;
    }
    //通过逆推获取
    Queue<DirectedEdge> allEdges = new Queue<>();
    while (true) {
      DirectedEdge e = edgeTo[v];
      //因为根节点的上一个节点是没有的,所以当为Null时候,就找到了根节点了
      if (e == null) {
        break;
      } else {
        allEdges.enqueue(e);
        //更新v的值
        v = e.from();
      }
    }
    return allEdges;
  }
}

松弛技术

松弛这个词来源于生活:一条橡皮筋沿着两个顶点的某条路径紧紧展开,如果这两个顶点之间的路径不止一条,还有存在更短的路径,那么把皮筋转移到更短的路径上,皮筋就可以放松了

松弛这种简单的原理刚好可以用来计算最短路径树

在我们的API中,需要用到两个成员变量edgeTo和distTo,分别存储边和权重,一开始给定一幅图G和顶点s,我们只知道图的边以及这些边的权重,其他的一无所知,此时初始化顶点s到顶点s的最短路径的总权重distTo[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的过程如下

Dijkstra算法实现

代码实现

DijkstraSPTest

public static void main(String[] args) throws Exception {
    //创建一幅加权有向图
    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 edgeNumbers = Integer.parseInt(br.readLine());
    for (int i = 1; i <= edgeNumbers; i++) {
      //4 5 0.35
      String line = br.readLine();
      String[] strs = line.split(" ");
      int v = Integer.parseInt(strs[0]);
      int w = Integer.parseInt(strs[1]);
      double weight = Double.parseDouble(strs[2]);
      DirectedEdge e = new DirectedEdge(v, w, weight);
      G.addEdge(e);
    }
    //创建DijkstraSP对象,查找最短路径树
    DijkstraSP sp = new DijkstraSP(G, 0);
    //查找最短路径,0->6的最短路径
    Queue<DirectedEdge> edges = sp.pathTo(6);
    //遍历打印
    for (DirectedEdge edge : edges) {
      System.out.println(edge.from() + "-->" + edge.to() + ": :" + edge.weight());
    }
  }
Last modification:August 5th, 2021 at 10:46 am