如下图:

就像上图, 每一个点可以理解成一个岔路口, 线段就是路径, 线段上的值为长度, 如何找到从 v0到各个岔路口的最小值, 也就是最短路径问题

• 如何使用代码表示出上图呢?

最短路径问题 和 深度广度搜索一样, 都是建立在图这个数据结构上的, 因此我们可以选用邻接表 或者是临接矩阵 来表示上图 , 封装类如下:

Copy
public class Graph01 {      // 使用邻接表的方式表示图     private LinkedList<Edge> [] graph ;     // 图中一共多少个点     private int size;      public Graph01(int size) {         this.size = size;         this.graph = new LinkedList[this.size];         for (int i = 0; i < size; i++) {             graph[i]=new LinkedList<>();         }     }      // 添加点的方法     public void addEdge(int s, int e, int w) {         this.graph[s].add(new Edge(s, e, w));     }

它大概长这个样子:

• 如何表示两点之间的边?

一条边有三个描述属性, 两边的顶点 + 权重

Copy
   // 边的封装类     private class Edge {         // 开始点的值         private int start;         // 结束点的值         private int end;         // 权重         private int weight;          public Edge(int start, int end, int weight) {             this.start = start;             this.end = end;             this.weight = weight;         }     } 

• 如何表示顶点

使用两个属性描述顶点, 分别是 dist 和 id , 比如我们描述 v3 , 那么它的id = 3 , dist是到起点v0的距离, 故 dist =13

Copy
  // 图中各个点的封装类     private class Vertex implements Comparable<Vertex> {         // 用户指定的起点到当前点的距离         private int dist;         // 顶点的id (v1 v2 中的 1 和 2)         private int id;          public Vertex(int dist, int startId) {             this.dist = dist;             this.id = startId;         }          @Override         public int compareTo