论文部分内容阅读
摘要:最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。本文采用JAVA语言来实现路径算法中的Johnson算法。
关键词:最短路径 Java Johnson算法 算法实现
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:确定起点的最短路径问题。即已知起始结点,求最短路径的问题;确定终点的最短路径问题。与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题;确定起点终点的最短路径问题。即已知起点和终点,求两结点之间的最短路径;全局最短路径问题——求图中所有的最短路径。
一、最短路径算法的实现策略
用于解决最短路径问题的算法被称作“最短路径算法”,有时被简称作“路径算法”。最常用的路径算法有:Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
所谓单源最短路径问题是指:已知图G=(V,E),我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先,我们可以发现有这样一个事实:如果P是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,∞]定义。因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost),边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(例如最短路径)。这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
二、代码实现
importjava.util.Scanner;
publicclassMain{
privatestaticintn;//G图中的顶点个数
privatestaticint[]distent=null;//最短路径长度
privatestaticint[]previous=null;//前驱顶点集合
publicstaticvoiddijkstra(intv,int[][]a,int[]dist,int[]prev){
//单源最短路径问题的Dijkstra算法
intn=dist.length-1;//问题的规模,0号元素未使用
if(v<1||v>n)return;//源不在图中,则返回
boolean[]s=newboolean[n 1];//判断点是否在集合S中
//初始化
for(inti=1;i<=n;i ){
dist[i]=a[v][i];//源到点i的最短特殊路径长度
s[i]=false;//点i现在不在集合s中
if(dist[i]==-1)
prev[i]=0;//若最短路径长度恒为-1表示无通路,则让点i的前驱点为0
else
prev[i]=v;//有通路则让点i的前驱指向源
}
dist[v]=0;
s[v]=true;//源放入集合s中
for(inti=1;i inttemp=Integer.MAX_VALUE;
intu=v;
//在剩下的点中除了没有通路的点中找到最容易到达的,并把最容易到达的放入u中
for(intj=1;j<=n;j ){
if((!s[j])
关键词:最短路径 Java Johnson算法 算法实现
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:确定起点的最短路径问题。即已知起始结点,求最短路径的问题;确定终点的最短路径问题。与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题;确定起点终点的最短路径问题。即已知起点和终点,求两结点之间的最短路径;全局最短路径问题——求图中所有的最短路径。
一、最短路径算法的实现策略
用于解决最短路径问题的算法被称作“最短路径算法”,有时被简称作“路径算法”。最常用的路径算法有:Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
所谓单源最短路径问题是指:已知图G=(V,E),我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先,我们可以发现有这样一个事实:如果P是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,∞]定义。因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost),边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(例如最短路径)。这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
二、代码实现
importjava.util.Scanner;
publicclassMain{
privatestaticintn;//G图中的顶点个数
privatestaticint[]distent=null;//最短路径长度
privatestaticint[]previous=null;//前驱顶点集合
publicstaticvoiddijkstra(intv,int[][]a,int[]dist,int[]prev){
//单源最短路径问题的Dijkstra算法
intn=dist.length-1;//问题的规模,0号元素未使用
if(v<1||v>n)return;//源不在图中,则返回
boolean[]s=newboolean[n 1];//判断点是否在集合S中
//初始化
for(inti=1;i<=n;i ){
dist[i]=a[v][i];//源到点i的最短特殊路径长度
s[i]=false;//点i现在不在集合s中
if(dist[i]==-1)
prev[i]=0;//若最短路径长度恒为-1表示无通路,则让点i的前驱点为0
else
prev[i]=v;//有通路则让点i的前驱指向源
}
dist[v]=0;
s[v]=true;//源放入集合s中
for(inti=1;i
intu=v;
//在剩下的点中除了没有通路的点中找到最容易到达的,并把最容易到达的放入u中
for(intj=1;j<=n;j ){
if((!s[j])