从A到B，有多条路线，要找出最短路线，应该用哪种数据结构来存储这些数据。

 

这不是显然的考查图论的相关知识了么，

1.图的两种表示方式：

邻接矩阵：二维数组搞定。

邻接表：Map<Vertext,List<Edge>>搞定。

其中邻接矩阵适用于稠密图，即图上的任意两点之间均（差不多都）存在一条边。

而A到B之间的路线，显然是稀疏图，果断的选用邻接表。

2.加权有向图最短路径问题，典型的dijkstra最短路径算法。

 

说干就干，翻翻《数据结构与算法》，自己用Java大概实现了一下，具体代码如下：

 

实现思路：

1，定义一个类：有向图类：Graph。

有向图类的子类：节点类：Vertex，边类：Vertex。

节点类：保存节点名称，上一个节点，长度等属性。

边节点：保存每条边的两边的节点，通过边找到对应的另一条节点。

2，该类有两个属性：

1，List
     
       vertexList：保存图的顶点集合，便于遍历顶点的时候查找对应集合。2，Map
      
       > ver_edgeList_map：图的每个顶点对应的有向边。
      
     

3，为了能够记录最短路径，需要为每个节点定义一个属性：父节点，表示父节点到该点的距离最短。

3，每个节点有多个属性：

String name;  //节点名字boolean known; //此节点之前是否已知，如果未知的话，则需要初始化距离adjuDist和parent属性int adjuDist; //保存从开始节点到此节点距离Vertex parent; //当前从初始节点到此节点的最短路径下，的父节点。

4，从起点节点开始查找。

比较规则：从A节点开始比较，对其指向的B节点进行初始化和比较：

如果B节点未被初始化，先设置该B节点的父节点为A节点，距离为边长加上A节点的adjuDist。

如果已经初始化完了，则重新比较：

如果A节点加边长小于B节点的adjuDist，则证明A节点到B节点的距离最短，设置A节点为B节点父节点，并且长度修改为A节点的adjuDist加上边长。

否则不做操作。

5，等所有的节点初始化完了，从终止节点开始，通过终止节点的父节点找到上一个节点，输出节点的路径。

 

代码如下：

package 笔试题;import java.util.LinkedList;import java.util.List;import java.util.Map; public class Graph{        private List
     
       vertexList;   //图的顶点集    private Map
      
       > ver_edgeList_map;  //图的每个顶点对应的有向边        public Graph(List
       
         vertexList, Map
        
         > ver_edgeList_map) {        super();        this.vertexList = vertexList;        this.ver_edgeList_map = ver_edgeList_map;    }     public List
         
           getVertexList() {        return vertexList;    }     public void setVertexList(List
          
            vertexList) { this.vertexList = vertexList; } public Map
           
            > getVer_edgeList_map() { return ver_edgeList_map; } public void setVer_edgeList_map(Map
            
             > ver_edgeList_map) { this.ver_edgeList_map = ver_edgeList_map; } static class Edge{ private Vertex startVertex; //此有向边的起始点 private Vertex endVertex; //此有向边的终点 private int weight; //此有向边的权值 public Edge(Vertex startVertex, Vertex endVertex, int weight) { super(); this.startVertex = startVertex; this.endVertex = endVertex; this.weight = weight; } public Edge() {} public Vertex getStartVertex() { return startVertex; } public void setStartVertex(Vertex startVertex) { this.startVertex = startVertex; } public Vertex getEndVertex() { return endVertex; } public void setEndVertex(Vertex endVertex) { this.endVertex = endVertex; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } } static class Vertex { private final static int infinite_dis = Integer.MAX_VALUE; private String name; //节点名字 private boolean known; //此节点之前是否已知 private int adjuDist; //此节点距离 private Vertex parent; //当前从初始节点到此节点的最短路径下，的父节点。 public Vertex() { this.known = false; this.adjuDist = infinite_dis; this.parent = null; } public Vertex(String name) { this.known = false; this.adjuDist = infinite_dis; this.parent = null; this.name = name; } public String getName() { return name; } public void setName(String name) { this.name = name; } public boolean isKnown() { return known; } public void setKnown(boolean known) { this.known = known; } public int getAdjuDist() { return adjuDist; } public void setAdjuDist(int adjuDist) { this.adjuDist = adjuDist; } public Vertex getParent() { return parent; } public void setParent(Vertex parent) { this.parent = parent; } /** * 重新Object父类的equals方法 */ @Override public boolean equals(Object obj) { if (!(obj instanceof Vertex)) { throw new ClassCastException("an object to compare with a Vertext must be Vertex"); } if (this.name==null) { throw new NullPointerException("name of Vertex to be compared cannot be null"); } return this.name.equals(obj); } } public void setRoot(Vertex v) { v.setParent(null); v.setAdjuDist(0); } /** * * @param startIndex dijkstra遍历的起点节点下标 * @param destIndex dijkstra遍历的终点节点下标 */ public void dijkstraTravasal(int startIndex,int destIndex) { Vertex start = vertexList.get(startIndex); Vertex dest = vertexList.get(destIndex); String path = "["+dest.getName()+"]"; setRoot(start); updateChildren(vertexList.get(startIndex)); int shortest_length = dest.getAdjuDist(); while((dest.getParent()!=null)&&(!dest.equals(start))) { path = "["+dest.getParent().getName()+"] --> "+path; dest = dest.getParent(); } System.out.println("["+vertexList.get(startIndex).getName() +"] to ["+ vertexList.get(destIndex).getName()+"] dijkstra shortest path :: "+path); System.out.println("shortest length::"+shortest_length); } /** * 从初始节点开始递归更新邻接表 * @param v */ private void updateChildren(Vertex v) { if (v==null) { return; } if (ver_edgeList_map.get(v)==null||ver_edgeList_map.get(v).size()==0) { return; } //用来保存每个可达的节点 List
             
               childrenList = new LinkedList
              
               (); for(Edge e:ver_edgeList_map.get(v)) { Vertex childVertex = e.getEndVertex(); //如果子节点之前未知，则进行初始化， //把当前边的开始点默认为子节点的父节点，长度默认为边长加边的起始节点的长度，并修改该点为已经添加过，表示不用初始化 if(!childVertex.isKnown()) { childVertex.setKnown(true); childVertex.setAdjuDist(v.getAdjuDist()+e.getWeight()); childVertex.setParent(v); childrenList.add(childVertex); } //此时该子节点的父节点和之前到该节点的最小长度已经知道了，则比较该边起始节点到该点的距离是否小于子节点的长度， //只有小于的情况下，才更新该点为该子节点父节点,并且更新长度。 int nowDist = v.getAdjuDist()+e.getWeight(); if(nowDist>=childVertex.getAdjuDist()) { continue; } else { childVertex.setAdjuDist(nowDist); childVertex.setParent(v); } } //更新每一个子节点 for(Vertex vc:childrenList) { updateChildren(vc); } } }
              
             
            
           
          
         
        
       
      
     

测试代码：

package 笔试题;import java.util.HashMap;import java.util.LinkedList;import java.util.List;import java.util.Map; import 笔试题.Graph.Edge;import 笔试题.Graph.Vertex; /** * 测试用main方法 * @author wuhui.wwh * */public class TestGraph {    public static void main(String[] args) {        Vertex v1= new Vertex("v1");        Vertex v2= new Vertex("v2");        Vertex v3= new Vertex("v3");        Vertex v4= new Vertex("v4");        Vertex v5= new Vertex("v5");        Vertex v6= new Vertex("v6");        Vertex v7= new Vertex("v7");        Vertex v8= new Vertex("v8");                List
     
       verList = new LinkedList
      
       ();        verList.add(v1);        verList.add(v2);        verList.add(v3);        verList.add(v4);        verList.add(v5);        verList.add(v6);        verList.add(v7);        verList.add(v8);                Map
       
        > vertex_edgeList_map = new HashMap
        
         >();                List
         
           v1List = new LinkedList
          
           (); v1List.add(new Edge(v1,v2,6)); v1List.add(new Edge(v1,v4,1)); v1List.add(new Edge(v1,v4,1)); List
           
             v2List = new LinkedList
            
             (); v2List.add(new Edge(v2,v3,43)); v2List.add(new Edge(v2,v4,11)); v2List.add(new Edge(v2,v5,6)); List
             
               v3List = new LinkedList
              
               (); v3List.add(new Edge(v3,v8,8)); List
               
                 v4List = new LinkedList
                
                 (); v4List.add(new Edge(v4,v3,15)); v4List.add(new Edge(v4,v5,12)); List
                 
                   v5List = new LinkedList
                  
                   (); v5List.add(new Edge(v5,v3,38)); v5List.add(new Edge(v5,v8,13)); v5List.add(new Edge(v5,v7,24)); List
                   
                     v6List = new LinkedList
                    
                     (); v6List.add(new Edge(v6,v5,1)); v6List.add(new Edge(v6,v7,12)); List
                     
                       v7List = new LinkedList
                      
                       (); v7List.add(new Edge(v7,v8,20)); vertex_edgeList_map.put(v1, v1List); vertex_edgeList_map.put(v2, v2List); vertex_edgeList_map.put(v3, v3List); vertex_edgeList_map.put(v4, v4List); vertex_edgeList_map.put(v5, v5List); vertex_edgeList_map.put(v6, v6List); vertex_edgeList_map.put(v7, v7List); Graph g = new Graph(verList, vertex_edgeList_map); g.dijkstraTravasal(0, 7); }}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

运行结果：

[v1] to [v8] dijkstra shortest path :: [v1] --> [v2] --> [v5] --> [v8]shortest length::25