迪杰斯特拉 (Dijkstra)算法求最短路径问题

目录
算法介绍
应用实例
算法步骤
代码实现
__

算法介绍
迪杰斯特拉（ Dijkstra ）算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。
应用实例

算法步骤
1）设置出发顶点为 v ，顶点集合 VfvI ,v2, vi .), v 到 V 各顶点的距离构成距离集合 Dis , Dis ( dI ,d2, di .), Dis 集合记录着 v 到图中各顶点的距离（到自身可以看作0, v 到 vi 距离对应为 di )
2）从 Dis 中选择值最小的 di 并移出 Dis 集合，同时移出 V 集合中对应的项点 vi ，此时的 v 到 vi 即为最短路径
3）更新 Dis 集合，更新规则为：比较 v 到 V 集合中顶点的距离值，与 v 通过 vi 到 V 集合中顶点的距离值，保留
值较小的一个（同时也应该更新顶点的前驱节点为 vi ，表明是通过 vi 到达的）
4）重复执行两步骤，直到最短路径顶点为目标顶点即可结束。
代码实现

2. import java.util.Arrays;
4. public class _最短路{
5. static int[] vis;//标记已经访问的顶点 0未访问 1 访问
6. static int[] dis;//出发顶点到各个下标对应顶点的最短距离
7. static int[] pre;//每个下标对应的上一个顶点下标
8. static char[] vertex;//顶点
9. static int[][] matrix;//邻接矩阵
10. public static void main(String[] args) {
11. vertex= new char[]{'A','B','C','D','E','F','G'};
12. matrix = new intvertex.length;
13. chushihua(matrix);//初始化邻接矩阵
14. djstl(vertex.length,6);//调用算法
15. }
16. public static void djstl(int length,int start) {
17. vis=new int[length];
18. dis=new int[length];
19. pre=new int[length];
20. Arrays.fill(dis, 9999);//初始化距离为较大值
21. dis[start] = 0;//初始化出发顶点到自身的距离0
23. / 先将起始点到与其连通的顶点的路径及pre前一个顶点进行更新/
24. update(start);
25. //在以与起始点相连的顶点为起点 更新距离和路径
26. for (int i = 1; i < vertex.length; i++) {
27. int minIndex = -1;
28. int mindis=9999;
29. //找到一个最短路径
30. for (int j = 0; j < vertex.length; j++) {
31. if(vis[j]==0 && dis[j] < mindis) {
32. minIndex = j;
33. mindis = dis[j];
34. }
35. }
36. vis[minIndex] = 1;
37. update(minIndex);//继续更新
38. }
40. System.out.println(Arrays.toString(dis));
41. }
42. /**
43. • 以index顶点向下查找！！！以起点start到index附近的邻接结点的最短路径!!!
44. • @param index
45. */
46. public static void update(int index) {
47. vis[index] = 1;//index标记为已访问
48. int len= 0;//len：从start顶点到index顶点的距离+上从index再到i顶点的距离
49. //循环遍历每个邻接结点顶点，找到真正意义上的最短路径
50. for (int i = 0; i < matrix[index].length; i++) {
51. //记录从start顶点到index顶点的距离+上从index再到i顶点的距离
52. len = dis[index] + matrixindex;
53. //将dis[i] 即从start直接到i 的距离 与len进行比较
54. if(vis[i] == 0 && len < dis[i]) {
55. dis[i] = len;//更新最短路径
56. pre[i] = index;//更新前置顶点
57. }
58. }
59. }
60. /**
61. • 初始化邻接矩阵
62. • @param matrix
63. */
64. public static void chushihua(int[][] matrix) {
65. final int N = 9999;
66. matrix[0]=new int[]{N,5,7,N,N,N,2};
67. matrix[1]=new int[]{5,N,N,9,N,N,3};
68. matrix[2]=new int[]{7,N,N,N,8,N,N};
69. matrix[3]=new int[]{N,9,N,N,N,4,N};
70. matrix[4]=new int[]{N,N,8,N,N,5,4};
71. matrix[5]=new int[]{N,N,N,4,5,N,6};
72. matrix[6]=new int[]{2,3,N,N,4,6,N};
73. }
74. }