H5+JAVA实现最短路径算法与地图显示(第三天)

再说下算法部分。

我参考了网上的一些算法。采用到的是 floyd算法。参考地址http://www.ddvip.com/tech/1000140659.html

嫌弃它广告太多，我还是把图抠过来了，如下：

再顺路搬一段文字过来:

初始状态：S是记录各个顶点间最短路径的矩阵。 
第1步：初始化S。 
     矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。实际上，就是将图的原始矩阵复制到S中。 
     注:a[i][j]表示矩阵S中顶点i(第i个顶点)到顶点j(第j个顶点)的距离。  

第2步：以顶点A(第1个顶点)为中介点，若a[i][j] > a[i][0]+a[0][j]，则设置a[i][j]=a[i][0]+a[0][j]。 
     以顶点a[1]6，上一步操作之后，a[1][6]=∞；而将A作为中介点时，(B,A)=12，(A,G)=14，因此B和G之间的距离可以更新为26。  

同理，依次将顶点B,C,D,E,F,G作为中介点，并更新a[i][j]的大小。

好了，算法的核心也就出来了，一直更新一个矩阵。

那么先来定义一些变量吧：

private static final int INF = Integer.MAX_VALUE;   // 最大值，处理两点之间无线断的权值。
int pointNum=points.size();
int n=pointNum;//总点数，从数据读取的
int path[][]=new int[n+1][n+1];//路径矩阵，记录点的前驱
int map[][]=new int[pointNum+1][pointNum+1];//构造权值矩阵
int dist[][]=map;//最终的最短路径矩阵 其实也可以之间用map

接下来是核心算法代码：

//算法算出所有点对点最短路径
for(int k=1; k<=n; k++) {
    for(int i=1; i<=n; i++) {
	for(int j=1; j<=n; j++) {
           // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
	  if(!(dist[i][k]==INF||dist[k][j]==INF)&&dist[i][j] > dist[i][k] + dist[k][j]) {
		 dist[i][j] = dist[i][k] + dist[k][j];
		 // "i到j最短路径"对应的路径，经过k
		 path[i][k] = i;
		 path[i][j] = path[k][j];
		   }
	    }
}

}

最终的写在后台的控制器的代码为:

@RequestMapping(value = "/test",produces="application/json;charset=utf-8", method = {RequestMethod.POST,RequestMethod.GET})
			public @ResponseBody JSONObject test(HttpSession session,
					@RequestParam(required = false) int from,
					@RequestParam(required = false) int to)
			{
					JSONObject obj=new JSONObject();
//					找到所有的点
					PointDAO pdao=new PointDAOImpl();
					LineDAO ldao=new LineDAOImpl();
					List<Point> points=pdao.findAllPoint();
					int pointNum=points.size();
					int n=pointNum;//总点数，从数据读取的
					int path[][]=new int[n+1][n+1];//路径矩阵，记录点的前驱
					int map[][]=new int[pointNum+1][pointNum+1];//构造权值矩阵
//					读取数据库，赋初值
					for(int i=1;i<=pointNum;i++) {
						for(int j=1;j<=pointNum;j++) {
							Line line=ldao.find(i, j);
								if(i==j) {
									map[i][j]=0;//自己到自己距离为0
								}
								else if(line==null) {//不存在此路径，权值为无穷大
									map[i][j]=INF;
								}
								else {
									map[i][j]=line.getLenth(); 
								}
						}
					}
//					打印输入的矩阵，便于控制台查看
					System.out.println("打印输入的矩阵");
					for(int i=1;i<=pointNum;i++) {
						for(int j=1;j<=pointNum;j++) {
							System.out.print(map[i][j]+"|");
						}
						System.out.println("");
					}
//					定义路径前驱
					int dist[][]=map;//最终的最短路径矩阵
				    for(int i=1; i<=n ; i++){
				        for(int j=1; j<= n; j++){
				          if(map[i][j]==0){
				               path[i][j] = -1;//表示  i -> j 不通 
				          }else{
				               path[i][j] = i;// 表示 i -> j 前驱为 i
				          }
				        }
				      }
//				    算法算出所有点对点最短路径
				    for(int k=1; k<=n; k++) {
				        for(int i=1; i<=n; i++) {
				          for(int j=1; j<=n; j++) {
				        	  // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
				            if(!(dist[i][k]==INF||dist[k][j]==INF)&&dist[i][j] > dist[i][k] + dist[k][j]) {
				              dist[i][j] = dist[i][k] + dist[k][j];
				              // "i到j最短路径"对应的路径，经过k
				              path[i][k] = i;
				              path[i][j] = path[k][j];
				            }
				          }
			        }
			      }
			    System.out.println("打印最终的矩阵");
			    for(int i=1;i&lt;=n;i++) {
					for(int j=1;j&lt;=n;j++) {
						System.out.print(dist[i][j]+"|");
					}
					System.out.println("");
				}
			    obj.put("lenth", dist[from][to]);

//				    倒序输出

List<Point> p=new ArrayList<Point>();

p.add(pdao.find(to));

while(path[from][to]!=from) {

System.out.print(path[from][to] +"----");

p.add(pdao.find(path[from][to]));

to = path[from][to];

}

p.add(pdao.find(from));

Collections.reverse(p);
			    obj.put("path", p);
			return obj;
		}</pre>

 
前台传过来两个参数，起始点和终结点，算法算出这两个点的最短路径以及经过的点，然后将结果存入JSONObject对象，传给前台。
下面是前台ajax请求的代码部分：
jQuery(document).on('click', ".searchPath", function() {
			var data={
				from:$("#searchFrom").val(),
				to:$("#searchTo").val()
			}
			jQuery.ajax({
				type: 'POST',
				 url: "test",
				 data:data,
				 dataType: 'json',
				 success: function(json) { 
					 var canvers=document.getElementById('mycanver');
						var cxt=canvers.getContext('2d');
								cxt.save(); 
								cxt.strokeStyle="red";
								cxt.translate(0.5,0.5); 
								cxt.lineWidth = 2; 
								cxt.beginPath(); 
								cxt.moveTo(json.path[0].x, json.path[0].y); 
								var text="最短路径为："+json.path[0].name;
								for(var i=1;i<json.path.length;i++){
									cxt.lineTo(json.path[i].x,json.path[i].y);
									text=text+"——>"+json.path[i].name;
								}
								$("#control").html(text+"\<br\>");
								$("#control").append("最短路径为："+json.lenth+"米\<br\>");
								$("#control").append("步行大约用时："+Math.ceil(json.lenth/60)+"分钟")
								cxt.stroke(); 
								cxt.restore(); 
						}
				});
		 });
差不多了就缺整体代码了，最后再更新。