首页 > 代码库 > Dijkstra算法应用之Java实现
Dijkstra算法应用之Java实现
缘来是你：
前几天在博客园里，有小伙伴贴出华为2010年10K（薪资）员工3级晋级试题。
问题主要是算法实现。
在师兄大批入住华为的环境下，作为一名热爱算法的小伙伴，也想小试一下身手。
问题地址：http://www.cnblogs.com/preacher/p/4126261.html
在解决上述问题前先来复习一下基础知识： Dijkstra最短路径算法
上述问题放在下一期随笔上
算法简析：
Dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。
设G=（V，E）是一个有向图，V表示顶点，E表示边。它的每一条边（i，j）属于E，都有一个非负权W（I,j），在G中指定一个结点v0，要求把从v0到G的每一个接vj（vj属于V）的最短有向路径找出来（或者指出不存在）。
Dijstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其他点的最短距离
基本思想是：
设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。
基本步骤：
1、把所有结点分成两组：
第一组：包括已经确定最短路径的结点；
第二组：包括尚未确定最短路径的结点。
2、开始时，第一组只包含起点，第二组包含剩余的点；
3、用贪心的策略，按最短路径长度递增的顺序把第二组的结点加到第一组去，直到v0可达的所有结点都包含于第一组中。在这个过程中，不断更新最短路径，总保持从v0到第一组各结点的最短路径长度dist都不大于从v0到第二组任何结点的路径长度。
4、每个结点对应一个距离值，第一组结点对应的距离就是v0到此结点的最短路径长度，第二组结点对应的距离值就是v0由第一组结点到此结点的最短路径长度。
5、直到所有的顶点都扫描完毕（v0可达的所有结点都包含于第一组中），找到v0到其它各点的所有最短路径。
动画演示：http://www.jcc.jx.cn/kejiandb/Dijkstra.swf
代码实现：
1 import java.util.Scanner; 2 3 4 public class DijkstraAl { 5 6 7 public static void main(String argv[] ){ 8 9 int k=0; int j=0; 10 Scanner br=new Scanner(System.in); 11 System.out.println("Please input the stations(int):"); 12 j=Integer.parseInt(br.nextLine()); 13 System.out.println("Please input the roads:(int):"); 14 k=Integer.parseInt(br.nextLine()); 15 System.out.println("Please input the rodas like‘1 2 3‘: from 1 station to 2 station length 3."); 16 String Sourcedata =http://www.mamicode.com/br.nextLine(); 17 String data[]=Sourcedata.split(" "); 18 br.close(); 19 int s[][]; 20 s=new int[j][]; 21 for(int i=0;i<j;i++){ 22 s[i]=new int[j]; 23 } 24 for(int i=0;i<j;i++){ 25 for(int p=0;p<j;p++){ 26 s[i][p]=10000; 27 if(i==p) 28 s[i][p]=0; 29 } 30 } 31 for(int i=0;i<3*k;i=i+3){ 32 int m=Integer.parseInt(data[i]); 33 int n=Integer.parseInt(data[i+1]); 34 s[m-1][n-1]=Integer.parseInt(data[i+2]); //实现的是无向图 35 s[n-1][m-1]=Integer.parseInt(data[i+2]); 36 } 37 /*for(int i=0;i<j;i++){ 38 for(int p=0;p<j;p++){ 39 System.out.print(s[i][p]+" "); 40 if(s[i][p]!=10000) 41 System.out.print(" "); 42 } 43 System.out.println(); 44 }*/ 45 46 distr(s, 0, j); 47 48 } 49 50 public static void distr(int[][] data, int j, int n){ 51 52 int[] Shortl,Chang; String[] route; 53 Chang=new int[n]; //记录需经过的station数 54 Shortl=new int[n]; //记录最短路径的长度 55 route=new String[n]; //记录最短路径的route stations 56 for(int i=0;i<n;i++){ 57 route[i]=""; 58 Shortl[i]=data[j][i]; 59 if(Shortl[i]>0&&Shortl[i]!=10000) 60 { route[i]=route[i]+" "+i; 61 Chang[i]=1; } 62 else 63 Chang[i]=0; 64 65 } 66 67 for(int i=0;i<n;i++){ 68 69 // System.out.println("The xunhuan time i:"+i); 70 for(int t=0;t<n;t++){ 71 72 // System.out.println("The xunhuan time t:"+t); 73 // System.out.println("The xunhuan time Shortl[t]:"+Shortl[t]); 74 if(Shortl[t]!=10000){ 75 // System.out.println("The xunhuan time Shortl[t]:"+Shortl[t]); 76 for(int m=0;m<n;m++){ 77 // System.out.println("The xunhuan time m and data[t][m]:"+m+" "+data[t][m]); 78 if(!(data[t][m]==10000)){ 79 // System.out.println("The xunhuan time m and data[t][m]:"+data[t][m]+Shortl[t]+Shortl[m]); 80 if((data[t][m]+Shortl[t]) < Shortl[m]){ 81 Shortl[m]=data[t][m]+Shortl[t]; 82 Chang[m]=Chang[t]+1; 83 route[m]=route[t]+" "+m; 84 // System.out.println("Change :"+Shortl[t]); 85 break; 86 } 87 } 88 } 89 90 } 91 } 92 93 94 } 95 for(int u=0;u<n;u++){ 96 System.out.println("The shortest route from 0 address to "+u+" address :"+Shortl[u]); 97 System.out.println("The stations:"+Chang[u]); 98 System.out.println("The routes:"+j+route[u]); 99 }100 } 101 }
实现演示：
Dijkstra算法应用之Java实现