最短路径算法java实现

⑴ 求java实现矩阵图上任意两点的最短路径源码

我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。

代码欣赏：

publicstaticintstep=1;

=newStringBuffer();

publicstaticint[][]maze={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1},

{1,0,1,0,0,0,1,0,1,1,1},

{1,0,0,0,1,0,1,0,0,0,1},

{1,0,1,1,0,0,1,0,0,1,1},//0代表可以通过，1代表不可通过

{1,0,1,0,1,1,0,1,0,0,1},

{1,0,0,0,0,0,0,0,1,0,1},

{1,0,1,0,1,0,1,0,1,0,1},

{1,0,0,1,0,0,1,0,1,0,1},

{1,1,1,1,1,1,1,1,1,1,1}};

publicstaticvoidmain(String[]args){

inti,j;//循环记数变量

Sample.way(1,1);//二维数组起始值从下标1，1开始

System.out.println("起点从坐标x=1,y=1开始");

System.out.println("终点坐标是x=8,y=9结束");

System.out.println("这是迷宫图表");

System.out.println("012345678910");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i=0;i<10;i++){

System.out.print(""+i+"‖");

for(j=0;j<11;j++)

System.out.print("-"+maze[i][j]+"-‖");

System.out.println("");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//打印显示步数

System.out.print(printStep.toString());

}

publicstaticbooleanway(intx,inty){

if(maze[8][9]==2)//代表递归终止条件（也就是当走出出口时标记为2）

returntrue;

else{

if(maze[y][x]==0){

maze[y][x]=2;

/*

*下面if判断条件代表当前坐标为基点，

*根据判断对当前位置进行递归调用：如：

*往上、往右上、往右、往右下、往下、

*往左下、往左、往左上的坐标是否可走，

*判断是否可走的返回条件是：

*2代表可通过、1代表不能通过、3表示已经走过，但是未能走通。

*/

if(way(x,y-1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x+1,y-1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x+1,y)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x+1,y+1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x,y+1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x-1,y+1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x-1,y)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x-1,y-1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}else{

maze[y][x]=3;

returnfalse;

}

}else

returnfalse;

}

}

复制代码前需要楼主自己创建个类

Sample.way(1,1);这句代码是我的类的静态调用，改下XXXXX.way(1,1);

XXXXX代表你创建的类。

下面是这个程序运行后的截图

⑵ 单源最短路径的Dijkstra算法

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。
3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。
4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。 SPFA实际上是Bellman-Ford基础上的队列优化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每条边(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

⑶ 用Java实现一个地铁票价计算程序，希望给出主要算法与数据结构

根据某市地铁线路图写一个地铁票价计算程序

需求描述：

1.计费规则：最低2元，超过5站以上每站加收0.5元，换乘重新起算，例如L1先坐4站，换乘L2再坐6站，结果就是2+2.5=5.5元

2.程序启动以后读取输入文件（in.txt），内容格式如：

L2-8,L2-2

X3,L3-8

....

每行表示一次行程，起点站和终点站之间用逗号分隔，行数不限

4.系统按最短路径方案（尽量少换乘且站数少，假设乘 客换乘一次用的时间相当于坐4个站）规划路线，计算票价，并把路线和票价输出到文件(out.txt)，内容格式如：

L2-8,L2-2=2.5:L2-8,L2-7,L2-6,L2-5,L2-4,L2-3,L2-2

X3,L3-8=4:X3,X4,L3-8

....

等号后面的表示票价和路径

地铁线路图如下：共有5条线路，X开头的站点表示 换乘车站

⑷ 求java算法源代码 求出汽车从起点S出发到达终点T的一条行驶路程最短的路线。

呵呵，你如果最短路径是m*n的这个前提就好算；如果最短不一定是m*n的话就成了一个迷宫问题同样求指点啊