迪杰斯特拉算法：使用图的广度优先遍历算法，比如先从G点出发，找到能与G直接连接的顶点，然后才从与G最近的A出发，找到与A相邻的节点。通过比较G到每个顶点的距离大小，筛选出到每个点的最短路径
代码：

/*** 迪杰斯特拉算法球最短路径问题*/
public class Dijkstra {public static void main(String[] args) {char[] vertexs = {'A','B','C','D','E','F','G'};final int N = 65535;//N表示两点之间不直连//邻接矩阵int[][] weight = {{N,5,7,N,N,N,2},{5,N,N,9,N,N,3},{7,N,N,N,8,N,N},{N,9,N,N,N,4,N},{N,N,8,N,N,5,4},{N,N,N,4,5,N,6},{2,3,N,N,4,6,N},};Graph graph = new Graph(vertexs, weight);graph.print();graph.dijkstra(6);graph.show();}
}//图
class Graph{private char[] vertexs;//顶点数组private  int[][] weight;//邻接矩阵private VisitedVertex vv;public Graph(char[] vertexs, int[][] weight) {this.vertexs = vertexs;this.weight = weight;}public void print(){for(int[] link:weight){System.out.println(Arrays.toString(link));}}/*** 迪杰斯特拉算法* @param index  初始节点*/public void dijkstra(int index){vv = new VisitedVertex(vertexs.length,index);update(index);for(int j = 1;j<vertexs.length;j++){//初始节点已经处理过了，所以需要处理vetexs.length - 1 次index = vv.updateArray();update(index);}}//输出结果public void show(){vv.show();}//更新index下标顶点到周围顶点的距离和前驱节点private void update(int index){int len = 0;//根据遍历我们邻接矩阵的 weight[index]行for(int j = 0;j<weight[index].length;j++){//这个距离是：初始顶点到index这个点的距离+index点的相邻节点的距离//比如index为A点，就是遍历A点的相邻节点//但是G到这个节点的距离就是GA的距离加上A到这个节点的距离len = vv.getDis(index)+weight[index][j];//如果j没有被访问过，并且len小于出发顶点到j点的距离，就要更新if(!vv.visited(j) && len<vv.getDis(j)){vv.updatePre(index,j);//更新j的前驱节点为indexvv.updateDis(j,len);//更新初始节点到j的距离为len}}}}class VisitedVertex{public int[] already_arr;//记录每个顶点是否访问过public int[] per_visited;//每个顶点对应的前驱节点的下标数组public int[] dis;//记录出发顶点到其他所有顶点的距离，如G为出发点，则会记录G到其他顶点的距离//构造器/**** @param length 顶点的个数* @param index  出发顶点对应的下标*/public VisitedVertex(int length,int index){this.already_arr = new int[length];this.per_visited = new int[length];this.dis = new int[length];//将初始节点设置为以访问this.already_arr[index] = 1;//初始化disArrays.fill(dis,65535);this.dis[index] = 0;//设置出发顶点到其他顶点的距离65535，到自己为0}//判断传入的节点是否访问过public boolean visited(int index){return already_arr[index] == 1;}/*** 更新出发顶点到index顶点的距离* @param index* @param len  距离*/public void updateDis(int index,int len){dis[index] = len;}/*** 更新pre顶点的前驱节点为index* @param index* @param pre*/public void updatePre(int index,int pre){per_visited[pre] = index;}/*** 返回出发顶点到index顶点的距离* @param index*/public int getDis(int index){return dis[index];}/*** 继续选择并返回新的访问节点，例如G结束以后，就是处理A节点,因为A离G最近* @return*/public int updateArray(){int min = 65536;int index = 0;for(int i = 0;i<already_arr.length;i++){if(already_arr[i] == 0 && dis[i]<min){min = dis[i];index = i;}}//将index设置为以访问already_arr[index] = 1;return index;}//显示最后的结果，即输出三个数组public void show(){System.out.println("===============================================================");for(int i :already_arr){System.out.print(i+" ");}System.out.println();System.out.println("===============================================================");for(int i:per_visited){System.out.print(i+" ");}System.out.println();System.out.println("===============================================================");for(int i:dis){System.out.print(i+" ");}}
}