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

本贴最后更新于 3571 天前,其中的信息可能已经时异事殊

再说下算法部分。

我参考了网上的一些算法。采用到的是 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(); 
						}
				});
		 });

差不多了就缺整体代码了,最后再更新。

 

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    20 引用 • 245 回帖 • 232 关注
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖 • 3 关注
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    118 引用 • 54 回帖 • 3 关注
  • Sillot

    Insights(注意当前设置 master 为默认分支)

    汐洛彖夲肜矩阵(Sillot T☳Converbenk Matrix),致力于服务智慧新彖乄,具有彖乄驱动、极致优雅、开发者友好的特点。其中汐洛绞架(Sillot-Gibbet)基于自思源笔记(siyuan-note),前身是思源笔记汐洛版(更早是思源笔记汐洛分支),是智慧新录乄终端(多端融合,移动端优先)。

    主仓库地址:Hi-Windom/Sillot

    文档地址:sillot.db.sc.cn

    注意事项:

    1. ⚠️ 汐洛仍在早期开发阶段,尚不稳定
    2. ⚠️ 汐洛并非面向普通用户设计,使用前请了解风险
    3. ⚠️ 汐洛绞架基于思源笔记,开发者尽最大努力与思源笔记保持兼容,但无法实现 100% 兼容
    29 引用 • 25 回帖 • 130 关注
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 708 关注
  • etcd

    etcd 是一个分布式、高可用的 key-value 数据存储,专门用于在分布式系统中保存关键数据。

    6 引用 • 26 回帖 • 545 关注
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    93 引用 • 122 回帖 • 619 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    10057 引用 • 45698 回帖 • 69 关注
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 38 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 50 关注
  • Anytype
    3 引用 • 31 回帖 • 28 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    42 引用 • 130 回帖 • 253 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    187 引用 • 831 回帖
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    7 引用 • 28 回帖
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 262 关注
  • OpenStack

    OpenStack 是一个云操作系统,通过数据中心可控制大型的计算、存储、网络等资源池。所有的管理通过前端界面管理员就可以完成,同样也可以通过 Web 接口让最终用户部署资源。

    10 引用 • 1 关注
  • RemNote
    2 引用 • 16 回帖 • 24 关注
  • 宕机

    宕机,多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态,也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态,也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 77 关注
  • Sphinx

    Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。

    1 引用 • 227 关注
  • PWA

    PWA(Progressive Web App)是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术,在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 183 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    15 引用 • 7 回帖
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 443 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖 • 1 关注
  • Access
    1 引用 • 3 回帖 • 1 关注
  • 快应用

    快应用 是基于手机硬件平台的新型应用形态;标准是由主流手机厂商组成的快应用联盟联合制定;快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。

    15 引用 • 127 回帖 • 3 关注