基于java的最短路径算法分析与实现

《基于java的最短路径算法分析与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于JAVA的最短路径算法分析与实现摘要：最短路径问题是图论研宄中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。本文采用JAVA语言来实现路径算法中的Johnson算法。关键词：最短路径javajohnson算法算法实现最短路径问题是图论研宄中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题。即已知起始结点，求最短路径的问题；确定终点的最短路径问题。与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图

2、中该问题等同于把所有路径方向反转的确定起点的问题;确定起点终点的最短路径问题。即已知起点和终点，求两结点之间的最短路径；全局最短路径问题__求图中所有的最短路径。一、最短路径算法的实现策略用于解决最短路径问题的算法被称作“最短路径h去”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。所谓单源最短路径问题是指：己知图G=（V，E），我们希望找出从某给定的源结点sev到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P

3、是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。笔者以3Dijkstra算法为例，Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它计算的节点很多，所以效率低下。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合，以E表示G中所有边的集合。（u、v）表示从顶点u到v有路径相连，而边的权重则由权重函数w:E—[0、0

4、0]定义。因此，w（u、v）就是从顶点u到顶点v的非负花费值（cost），边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到S到t的最低花费路径（例如最短路径）。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。二、代码实现importjava.util.Scanner;publicclassMain{privatestaticintn;//G图中的顶点个数privatestaticint[]distent=null;//最短路径长度private

5、staticint[]previous=null;//前驱顶点集合publicstaticvoiddijkstra(intv,int[][]a,int[]dist,int[]prev){//单源最短路径问题的Dijkstra算法intn=dist.length-1;//问题的规模，0号元素未使用if(vn)return;//源不在图中，则返回boolean[]s=newboolean[n+l];//判断点是否在集合S中//初始化for(inti=l;i