雷竞技网页版研究和评论——国际期刊雷竞技苹果下载

国际期刊的创新在计算机和通信工程的研究

菜单

ISSN在线(2320 - 9801)打印(2320 - 9798)

所有提交的电磁系统将被重定向到在线手稿提交系统。作者请直接提交文章在线手稿提交系统各自的杂志。

Dijkstra’道路网络最短路径算法

K.Rohila1,P.Gouthami1Priya毫米2
  1. 女士(SE)、信息技术与工程学院维特大学,Vellore,泰米尔纳德邦,印度
  2. 助理教授(高级)、信息技术与工程学院维特大学,Vellore,泰米尔纳德邦,印度
相关文章Pubmed,谷歌学者

访问更多的相关文章国际期刊的创新在计算机和通信工程的研究

国际期刊的创新在计算机和通信工程的研究

文摘

最短路径问题是不可避免的在城市道路网络应用,如紧急处理和驱动导向系统。交通网络分析的基本概念与问题探讨。城市之间的交通状况变化从时间到时间和通常有大量的请求发生时,它需要快速找到解决方案。能解决上述问题,通过使用迪杰斯特拉最短路径的算法。的主要目标是实现的低成本。最短路径问题是两个顶点之间找到一个路径(节点)在一个给定的图,这样重量的总和构成边缘最小化。这个问题已持续多年的深入研究,由于其广泛的应用于图论,人工智能、计算机网络和交通系统的设计。经典的迪杰斯特拉算法旨在解决singlesource最短路径问题的静态图。它从源节点和整个网络计算最短路径。指出一个上界的两个节点之间的距离可以提前计算在给定的交通网络。 In order to solve the problem, we have been implemented shortest path for road network by using Applets in a programing language java. Software required for this application is jdk1.7.0_01.

关键字
最短路径;迪杰斯特拉算法;广度优先搜索;最大数量的节点;

介绍
本文中说明两点之间最好的旅行方式,在这一过程中,最短路径算法。迪杰斯特拉算法是图搜索算法解决单源最短路径问题的图形与非负边路径成本,生产一个最短路径树。这种算法通常用于路由和其他网络相关协议。对于一个给定的源点(节点)图中,最短路径的算法发现Sfinding成本从一个顶点到一个目的地顶点通过停止算法一旦到目标点的最短路径被确定。例如,如果图的顶点代表城市和边缘路径成本代表驾驶对城市间的距离由直接连接路,迪杰斯特拉算法可以用来找到一个城市和其他城市之间的最短路线。
做了大量的工作寻找最短路径通过抽象。迪杰斯特拉算法的最短路径查找算法是应用于图指示,边缘和非负权重加权。如果我们有一个与边缘未加权的无向图,我们可以解决这个问题的实现广度优先搜索(BFS)算法。我们知道我们是unableto使用BFS算法的加权有向图,但我们可以修改BFS算法以这样一种方式,我们可以处理,上面提到的问题(权重和方向)。稍后我们将知道thatDijkstra算法是渐近最快的已知的单源最短路径算法与无界的非负权重任意的有向图。这些动机'that将帮助我们进一步了解Dijkstra算法的算法。

相关工作
室内导航援助为这种类型的用户[1]提出了额外的挑战所面临的不是传统的制导系统,由于个人交流的本质。算法是整体的一部分,室内导航模型,用于提供协助和指导在陌生的室内环境。操作路径规划使用Dijkstra的shortestpathalgorithms,“智能地图”,这是基于一种新的数据结构称为“仙人掌树”,这是基于不同的对象之间的关系,体现了室内环境。本研究探讨了潜在的设计申请视障即使-日期的定位和跟踪系统不能提供可靠的位置信息,这种类型的应用程序所需的高度。公共交通系统的最佳途径问题[3],我们发现转移的本质是,它需要额外的成本优势相邻边。所以,我们使用直接/间接相邻边加权有向图作为一个公共交通数据模型,提高存储邻接矩阵。我们介绍了空间存储结构来存储分散信息传递的间接相邻边列表。因此,我们解决问题的复杂网络图的存储和设计一种新的最短路径算法来解决交通问题的基础上,数据模型。算法分析展示,数据模型之前,我们提出的算法是一个简单的图根据Dijkstra算法的算法的时间和空间。今天,增加交通和复杂的现代roadnetwork已经找到一个好的路线[4]从一个位置到另一个非平凡的任务。提出了许多搜索算法来解决这个问题,和最著名的迪杰斯特拉算法,约翰逊的算法。虽然这些算法有效的路径发现,他们浪费的计算。 In this paper, we present a study to examine both uninformed search and heuristic search based on some major cities and towns.Efficient usage of routing algorithms [16] can significantly reduce travelling distance and transportation costs as well. Usage of the shortest-path algorithm in this case Dijkstra's algorithm for inner transportation optimization in warehouses. The model integrates data such as: 2D graph of warehouse layout, its 3D extension, historical data, ABC analysis and business process model. The prototype of proposed application is tested with sample data and by simulating different working conditions.

迪杰斯特拉算法
让我们开始的节点被称为初始节点。迪杰斯特拉算法将分配一些initialdistance值并将试图改善他们一步一步。第一次迭代,当前路口的起点和距离会是零。后续的迭代(第一次)后,当前路口将最接近,并且交叉从这将容易找到。
从当前交叉路口、更新每一个既无交集的距离是直接连接到它。这是通过确定的总和之间的距离既无交叉和当前路口的价值和重新确认,并且交叉路口这个值是否小于其当前值。实际上,十字路口是重新包装如果路径通过当前的十字路口是比前面短路径。促进最短路径识别、用铅笔、马克箭头指向重新命名的道路十字路口如果标签/重新贴标签于它,并删除所有他人指向它。更新每个相邻路口的距离之后,马克当前交叉路口作为访问并选择theunvisited交点与最低距离(从起点)或最低列为当前交叉路口。节点标记为访问标记起点的最短路径,将不会被重提或返回。
图像

实验结果
在本节中,我们进行实验比较节点之间的路径。在这个路径,最短路径是由使用迪杰斯特拉算法。这里的最短路径,这意味着低成本被发现的最短路径算法。在java代码中使用applet, applet查看器显示的最短路径。使用java软件在报告中显示的结果。我们有成功的结果。实验是成功完成。这个项目的结果发现单个源的最短路径所有成对的使用迪杰斯特拉算法的顶点。它给最便宜的成本和它的实现是很容易的。
初始:
算法运行:红色箭头指向的节点可以从开始节点。
距离:b = 55 d = 50, f = 100。节点d的最小距离。没有其他箭头进入d d。节点将橙色显示50 d最短路径的长度。
b .决赛:
橙色箭头指向节点的可及节点已经有一个最终的距离。距离:c = 68。没有其他箭头到c。
节点c将橙色显示68 c的最短路径的长度。算法结束,按照橙色箭头从开始节点任意节点的最短路径的节点。

结论
我们已经提出了一个实用的算法在交通网络最短路径问题。该算法可以限制搜索子图指出基于给定节点的两个节点之间的距离。结果,最短路径的计算进行了简化。实验结果在实际道路网络反映的潜在特征算法相比,现有的工作。
applet可以被证明是非常有用的,所有的学生。每个学生希望了解的人的一个算法,实现在这个工具,可以使用该applet从任何远程位置,可能他的家。不管他的系统是什么。它只要求Java虚拟机(JVM),安装到他的系统。应该指出,从Sun Microsystems JVM免费下载。而且有一个打算提高图形编辑器,以便用户能够画无向图,或网络。然而这个applet可以进一步丰富,可能可视化算法直观。定向网络等原始单纯形算法,解决了网络最小费用流问题(MCNFP)。除了将添加更多的算法等无向图克鲁斯卡,一本正经的算法解决最小生成树(MST)问题。

未来的工作
在未来的版本中applet将被修改,为了执行独立的Java应用程序。此外,某些调查问卷将会给我们系的学生填写,为了得到反馈。这是非常重要的,以改善和评估教学效果的applet在现实教学环境。也会鼓励学生构建自己的applet。

数据乍一看
图1 图2
图1 图2

引用











全球技术峰会