通过Graph结构求解城市间最短路径
问题描述： 已知某地区的多个城市与部分城市之间的最短距离，求给定的两个城市之间的最短路径。
例如：已知城市A、B、C、D、E、F六座城市，城市之间的最短距离情况如下(可以为有向或者无向，这里以无向为例)：
A——B：2km
A——C：9km
A——E：3km
B——D：3km
C——E：5km
C——D：2km (F城作为边界条件，故上述无到达F城的路径，实际使用中可以不予考虑)
要求求出A城到其他各城的最短路径，或A城到指定城市(如D城)的最短路径。
解决思路： 上述问题属于典型的求顶点间最优路径的问题，借助图论进行求解。将各城市作为图的顶点，城市间的路径作为图的边，路径长度为对应边的权重构造图，之后采用Dijkstra算法求解最优路径。本文用java实现的代码，是在徐明远等编所著《Java常用算法手册》的示例代码【程序7-5】的基础上优化所得，封装了一部分属性使代码易用已读。代码如下：
首先新建Graph类文件以存储数据
/**
* 新建Graph类，用于存储数据
*@author Misui_user
*
*/
class GraphMatrix
{
public static final int MaxValue=65535; //最大值(可设为一个最大整数)
char[] Vertex; //保存顶点信息(序号或字母)
int GType=0; //图的类型(0:无向图，1:有向图)
int VertexNum; //顶点的数量
int EdgeNum; //边的数量
int[][] EdgeWeight; //保存边的权
/**
* 设置顶点
*@param points
*/
public void setVertex(char[] points){
this.Vertex=new char[points.length];
this.VertexNum=points.length;
for(int i=0;i
{
this.Vertex[i]=points[i]; //保存到各顶点数组元素中
}
}
/**
* 设置边及其权重
*@param roads
*@param weights
*/
public void setEdgeWeight(char[][] roads,int[] weights){
this.EdgeWeight=new int[roads.length][roads.length];
ClearGraph();
this.EdgeNum=roads.length;
for(int k=0;k
{
int i=indexOf(roads[k][0]); //在已有顶点中查找始点位置
int j=indexOf(roads[k][1]); //在已有顶点中查找结终点 位置
this.EdgeWeight[i][j]=weights[k]; //对应位置保存权值，表示有一条边
if(this.GType==0) //若是无向图
{
this.EdgeWeight[j][i]=weights[k]; //在对角位置保存权值
}
}
}
/**
* 清空邻接矩阵
*@param GM
*/
private void ClearGraph()
{
for(int i=0;i
{
for(int j=0;j
{
this.EdgeWeight[i][j]=MaxValue; //设置矩阵中各元素的值为MaxValue
}
}
}
public int indexOf(char c){
for(int i=0;iif(c==Vertex[i]){
return i;
}
}
return -1;
}
}
新建操作类，实现Dijkstra算法
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class DisMinGraph {
static final int MaxValue=65535; //最大值(可设为一个最大整数)
static Scanner input=new Scanner(System.in);
public static void main(String[] args) {
GraphMatrix GM=new GraphMatrix(); //定义保存邻接表结构的图
System.out.printf("求解最短路径问题！\n");
int VertexNum=input.nextInt(); //输入图顶点数
int EdgeNum=input.nextInt(); //输入图边数
char[] points=new char[VertexNum]; //读取顶点信息
char[][] roads=new char[EdgeNum][2]; //读取边信息,起点和终点
int[] weight=new int[EdgeNum]; //读取边权重
for(int i=0;i0];
}
for(int i=0;i0]=(input.next().toCharArray())[0];
roads[i][1]=(input.next().toCharArray())[0];
weight[i]=input.nextInt();
}
CreateGraph(GM,points,roads,weight); //生成邻接表结构的图
// OutGraph(GM); //输出邻接矩阵
int vend=GM.indexOf((input.next().toCharArray())[0]); //获取出发点位置
if(vend==-1){
System.out.println("顶点不存在，请重新输入！");
return;
}
int[][] disMin=DistMin(GM,vend); //执行最小路径算法
System.out.println("各顶点到达顶点“"+GM.Vertex[vend]+"”的最短路径分别为(起始点 - 结束点):");
for(int i=0;i//各个顶点到出发点的路径
{
char[][] path=getPath(GM,disMin,vend,i);
System.out.println("-->"+Arrays.toString(path[0])+"-------------->路径长度："+(int)path[1][0]);
}
}
private static void CreateGraph(GraphMatrix GM,char[] points,char[][] roads,int[] weights){ //创建邻接矩阵图
GM.setVertex(points);
GM.setEdgeWeight(roads, weights);
}
/**
* 输出图的邻接矩阵
*@param GM
*/
public static void OutGraph(GraphMatrix GM)
{
int i,j;
System.out.print("\n");
for(i=0;ifor(j=0;jif(GM.EdgeWeight[i][j]==MaxValue) //若权值为最大值
{
System.out.print("\tZ"); //以Z表示无穷大
}
else
{
System.out.print("\t"+GM.EdgeWeight[i][j]); //输出边的权值
}
}
System.out.print("\n");
}
}
/**
* 通过遍历图，生成可到达指定顶点的顶点数组tmpvertex，以及各顶点到达指定定点路径缓存数组path，实现Dijkstra算法
*@param GM
*@param vend
*@return 数组tmpvertex与数组path，联合表示指定顶点(出发点)到达各顶点的最小路径
*/
private static int[][] DistMin(GraphMatrix GM,int vend) //最短路径算法
{
//可到达指定顶点(出发点)的顶点集合，下标表示顶点位置，值表示是否可以到达，0表示不能，1表示能
int[] tmpvertex=new int[GM.VertexNum];
//从所有顶点到达指定顶点(出发点)的路径索引数组；下标为对应顶点，值为对应顶点可到达的下一个顶点
int[] path=new int[GM.VertexNum];
int[] weight=new int[GM.VertexNum]; //某终止点到各顶点的最短路径长度
for(int i=0;i//初始weight数组
{
tmpvertex[i]=0; //初始化顶点集合为空
weight[i]=GM.EdgeWeight[vend][i]; //保存最小权值
if(weight[i]0) //有效权值
{
path[i]=vend; //保存边
}
}
tmpvertex[vend]=1; //选入顶点vend
weight[vend]=0;
for(int i=0;iint min=MaxValue;
int k=vend;
for(int j=0;j//查找未用顶点的最小权值
{
if(tmpvertex[j]==0 && weight[j]1; //将顶点k选为可到达指定定点(出发点)
for(int j=0;j//以顶点k为中间点，重新计算权值 ，判断是否有以顶点k为中继到达指定定点(出发点)权值更小的点
{
if(tmpvertex[j]==0 && weight[k]+GM.EdgeWeight[k][j]return new int[][]{tmpvertex,path};
}
/**
* 输出指定顶点(出发点)到特定顶点end的路径和该路径的长度
*@param GM 图对象
*@param disMin 经DistMin()方法计算后得到的最小路径表示结果
*@param vend 出发点的位置
*@param end 结束点的位置
*@return 返回结果为路径与该路径的长度,result[0]为路径，result[1][0]为长度
*/
public static char[][] getPath(GraphMatrix GM,int[][] disMin,int vend,int end){
ArrayListpath=new ArrayList();
int l=0;
if(disMin[0][end]==1)
{
int k=end;
while(k!=vend)
{
path.add(GM.Vertex[k]);
l+=GM.EdgeWeight[k][disMin[1][k]];
k=disMin[1][k];
}
path.add(GM.Vertex[k]);
}
char[] p=new char[path.size()];
for(int i=0;ireturn new char[][]{p,{(char)l}};
}
}
测试用例
//输入顶点数量
6
//输入边数量
7
//输入顶点
A
B
C
D
E
F
//输入边及其权重
A B 2
A C 9
A E 3
B D 3
C E 5
D E 2
C D 2
//输入出发点名称
A
测试结果：
各顶点到达顶点“A”的最短路径分别为(起始点 - 结束点):
–>[A]————–>路径长度：0
–>[B, A]————–>路径长度：2
–>[C, D, B, A]————–>路径长度：7
–>[D, B, A]————–>路径长度：5
–>[E, A]————–>路径长度：3
–>[]————–>路径长度：0
用例的测试结果输出了A城到所有其他各城的最优路径，实际上是多次调用了DisMinGraph.getPath(GraphMatrix GM,int[][] disMin,int vend,int end)方法将所有城市到A城的路径分别进行了计算，如果需要返回指定城市(A城、D城)之间的距离，可在调用DisMinGraph.DistMin(GraphMatrix GM,int vend)方法对指定顶点使用Dijkstra算法后(这里的(指定顶点)必须是A或者D)，再调用getPath方法即可获得两城之间的最优路径信息。
上述代码，除可以解决无向图的顶点间最有路径问题外，还可以解决有向图的最优路径问题，切换GraphMatrix.GType属性即可。