单源最短路径问题（Java）
1、问题描述
给定 带权有向图 G=(V,E),其中每条边的权是 非负实数 。另外，还给定V中的一个顶点， 称为 源 。现在要计算 从源到所有其他各顶点的最短路长度 。这里路的长度是指路上各边权之和。这个问题通常称为 单源最短路径问题 。
其中，V表示顶点集合，E表示各个节点之间的边。
2、算法思路
对于单源最短路径问题， Dijkstra算法 是解决这个问题的 贪心 算法。
基本思想
设置 顶点集合S 并不断地做 贪心 选择来 扩充 这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时，S 中仅含有源。设u是G 的某一个顶点，把从源到u且中间只经过S中顶点的路称为 从源到u 的特殊路径 ，并用 数组dist 记录 当前每个顶点所对应的最短特殊路径长度 。
Dijkstra 算法每次从v-s中取出具有 最短特殊路长度的顶点u ,将u添加到S中，同时对数组dist 进行必要的修改。一旦S包含了所有V中顶点，dist数组就记录了从源到所有其他顶点之间的最短路径长度。
Dijkstra 算法可描述如下：
其中， 输入的带权有向图是G = （V, E) , V = {1 , 2, …, n} 。顶点v是源。a是一个二维数组，a[i][j]表示边(i,j)的权。当(i, j) 时，a[i][j]是一个大数。如dist[i]表示当前从源到顶点t的最短特殊路径长度。
3、代码实现
例如，对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。
题目示意图
importjava.util.ArrayList; importjava.util.Arrays; importjava.util.List; importjava.util.Scanner; /*** TODO 1 --> 4 --> 3 --> 5*/publicclassSolution { privatestaticintvNum, eNum; privatestaticint[] v; privatestaticfloat[][] e; publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); System.out.print("input the number of vertix and edge:"); vNum=scanner.nextInt(); eNum=scanner.nextInt(); v=newint[vNum]; e=newfloat[vNum+1][vNum+1]; for (inti=0; i<e.length; i++) { for (intj=0; j<e.length; j++) { e[i][j] =Float.MAX_VALUE; } } System.out.print("input the vertix information:"); for (inti=0; i<v.length; i++) { v[i] =scanner.nextInt(); } System.out.println("input the weight of edges:"); for (inti=0; i<eNum; i++) { intstart=scanner.nextInt(), target=scanner.nextInt(); e[start][target] = (float) scanner.nextInt(); } System.out.print("顶点有："); for (inti=0; i<v.length; i++) { if (i==v.length-1) { System.out.println(v[i]); } else { System.out.print(v[i] +", "); } } System.out.println("边与边之间的距离："); for (inti=1; i<e.length; i++) { for (intj=1; j<e.length; j++) { if (i!=j&&e[i][j] !=Float.MAX_VALUE) { System.out.print("["+i+", "+j+"] = "+e[i][j] +"; "); } } } System.out.println(); int[] path=newint[vNum+1]; float[] dist=newfloat[vNum+1]; Dijkstra(v[0], e, dist, path); System.out.print("Dijkstra路径为："); List<Integer>list=newArrayList<>(); list.add(vNum); list.add(path[vNum]); while (true) { if (path[list.get(list.size() -1)] ==1) { list.add(1); break; } list.add(path[list.get(list.size() -1)]); } for (intj=list.size() -1; j>=0; j--) { if (j!=0) { System.out.print(list.get(j) +"-->"); } else { System.out.println(list.get(j)); } } System.out.println("从顶点1到各顶点最短距离："); for (inti=1; i<dist.length; i++) { System.out.println("dist["+i+"] = "+dist[i]); } } publicstaticvoidDijkstra(intvertix, float[][] weight, float[] dist, int[] path) { intn=dist.length-1; if (vertix<1||vertix>n+1) { return; } boolean[] vis=newboolean[n+2]; // initializefor (inti=1; i<=n; i++) { dist[i] =weight[vertix][i]; vis[i] =false; if (dist[i] ==Float.MAX_VALUE) { path[i] =0; } else { path[i] =vertix; } } dist[vertix] =0; vis[vertix] =true; for (inti=1; i<n; i++) { floattmp=Float.MAX_VALUE; intu=vertix; for (intj=1; j<=n; j++) { if ((!vis[j]) && (dist[j] <tmp)) { u=j; tmp=dist[j]; } } vis[u] =true; for (intj=1; j<=n; j++) { if ((!vis[j]) && (weight[u][j] <Float.MAX_VALUE)) { floatnewDist=dist[u] +weight[u][j]; if (newDist<dist[j]) { dist[j] =newDist; path[j] =u; } } } } } }
运行结果
Dijkstra算法的迭代过程：
图解过程
4、算法正确性和计算复杂性
4.1 贪心选择性质
（1）根据算法可知，最短距离是最小的路长，故 dist[x]<= d(v,x)
（2）假设存在另外一条更短路红色线所示，故 d(v,x)+d(x,u)=d(v,u)<dist[u]
（3）由（1）（2）可知，dist[x]<dist[u]。此为矛盾，因为如果（3）成立，此时应该选择 x进入S集合，即选择具有最短特殊路径的顶点是x，而不是u。（因为根据最短路径算法，总是选取最短路径的顶点进入S）
4.2 最优子结构性质
该性质描述为：如果S(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么S(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设S(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有S(i,j)=S(i,k)+S(k,s)+S(s,j)。而S(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径S'(k,s)，那么S'(i,j)=S(i,k)+S'(k,s)+S(s,j)<S(i,j)。则与S(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
4.3 计算复杂性
对于具有n个顶点和e条边的带权有向图， 如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n) 时间。这个循环需要执行n-1次，所以完成循环需要
0(n2）时间。算法的其余部分所需要时间不超过0(n2）。
5、参考资料
- 算法设计与分析（第四版）
