本文目录一览：
- 1、用java求最短路径问题，求源程序
- 2、java 最短路径算法 如何实现有向 任意两点的最短路径
- 3、求java实现矩阵图上任意两点的最短路径源码
用java求最短路径问题，求源程序
import java.util.Vector;
public class Link {
private Vector link = new Vector();
// private Link next = null;
public Link() {
}
public boolean addNode(Node setNode){//增加一个节点
setNode = checkNode(setNode);
if(setNode != null){
this.link.addElement((Node)setNode);
return true;
}
return false;
}
public void delNode(Node setNode){ //删除一个节点
if(!this.link.isEmpty()){
for(int i=0;i this.link.size(); i++)
{
if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){
this.link.remove(i);
//System.out.println("asdfasdfas:"+this.link.size());
break;
}
}
}
}
public Node checkNode(Node setNode){//判断节点是否在链表里面并取得两者的最佳值
if(!this.link.isEmpty() setNode!=null){
for(int i=0;i this.link.size(); i++)
{
if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){
if(setNode.getStep() ((Node)this.link.elementAt(i)).getStep()){
setNode = (Node)this.link.elementAt(i);
this.link.remove(i);
}
else
return null;
break;
}
}
}
return setNode;
}
public boolean isEmpty(){
return this.link.isEmpty();
}
public Node getBestNode(){ //得到最好的节点
Node tmpNode = null;
if(!this.link.isEmpty()){
tmpNode = (Node)this.link.elementAt(0);
//System.out.println("tmpNodeStep:"+tmpNode.getStep());
//System.out.print("OpenNode(pos,step):");
for(int i=1;i this.link.size(); i++)
{
//System.out.print("("+((Node)this.link.elementAt(i)).getPos()+","+((Node)this.link.elementAt(i)).getStep()+")");
if(tmpNode.getJudgeNum() = ((Node)this.link.elementAt(i)).getJudgeNum()){
tmpNode = (Node)this.link.elementAt(i);
}
}
}
return tmpNode;
}
}
public class FindBestPath {
private char[][] map = null;//地图
private int maxX,maxY;//最大的地图边界大小
Node startNode = null;//入口
Node endNode = null;//出口
private int endX,endY;
/*初始化
*@param setMap 地图
*@param setX,setY 边界值
//////////*@param startNode 入口
//////////*param endNode 出口
*@param sX,sY:开始点
*@param eX,eY:结束点
*/
public FindBestPath(char[][] setMap,int setX,int setY,int sX,int sY,int eX,int eY) {
this.map = setMap;
this.maxY = setX - 1; //x,y互换
this.maxX = setY - 1; //x,y互换
//this.startNode = sNode;
//this.endNode = eNode;
Node sNode = new Node();
Node eNode = new Node();
sNode.setFarther(null);
sNode.setPos(posToNum(sX,sY));
sNode.setStep(0);
eNode.setPos(posToNum(eX,eY));
this.startNode = sNode;
this.endNode = eNode;
this.endX = eX;//numToX(eNode.getPos());
this.endY = eY;//numToY(eNode.getPos());
}
public int posToNum(int x,int y){//从xy坐标获得编号
return (x+y*(this.maxY+1));
}
public int numToX(int num){//从编号获得x坐标
return (num%(this.maxY+1));
}
public int numToY(int num){//从编号获得y坐标
return (int)(num/(this.maxY+1));
}
public boolean checkVal(int x,int y){//判断是否为障碍
//System.out.println("map["+x+"]["+y+"]="+map[x][y]);
if(this.map[x][y] == 'N')
return false;
else
return true;
}
public int judge(Node nowNode){//一定要比实际距离小
//System.out.println("nowNodePos:"+nowNode.getPos());
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
int distance = Math.abs((nowX-this.endX))+Math.abs((nowY-this.endY));
// System.out.println("distance:"+distance);
return distance;
}
public Node getLeft(Node nowNode){//取得左节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowY 0){//判断节点是否到最左
if(checkVal(nowX,nowY-1)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX,nowY-1));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Node getRight(Node nowNode){//取得右节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowY this.maxX){//判断节点是否到最左
if(checkVal(nowX,nowY+1)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX,nowY+1));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Node getTop(Node nowNode){//取得上节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowX 0){//判断节点是否到最左
if(checkVal(nowX-1,nowY)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX-1,nowY));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Node getBottom(Node nowNode){//取得下节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowX this.maxY){//判断节点是否到最左
if(checkVal(nowX+1,nowY)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX+1,nowY));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}
public Link getBestPath(){//寻找路径
Link openLink = new Link();//没有访问的路径
Link closeLink = new Link();//访问过的路径
Link path = null;//最短路径
Node bestNode = null;
Node tmpNode = null;
openLink.addNode(this.startNode);
while(!openLink.isEmpty())//openLink is not null
{
bestNode = openLink.getBestNode();//取得最好的节点
//System.out.println("bestNode:("+numToX(bestNode.getPos())+","+numToY(bestNode.getPos())+")step:"+bestNode.getJudgeNum());
if(bestNode.getPos()==this.endNode.getPos())
{
/*this.endNode.setStep(bestNode.getStep()+1);
this.endNode.setFarther(bestNode);
this.endNode.setJudgeNum(bestNode.getStep()+1);*/
path = makePath(bestNode);
break;
}
else
{
tmpNode = closeLink.checkNode(getLeft(bestNode));
if(tmpNode != null)
//System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getRight(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getTop(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getBottom(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);
openLink.delNode(bestNode);
closeLink.addNode(bestNode);
}
}
return path;
}
public Link makePath(Node lastNode){//制造路径
Link tmpLink = new Link();
Node tmpNode = new Node();
int x,y;
tmpNode = lastNode;
if(tmpNode != null){
do{
x=numToX(tmpNode.getPos());
y=numToY(tmpNode.getPos());
System.out.println("map["+x+"]["+y+"]="+map[x][y]);
tmpLink.addNode(tmpNode);
tmpNode = tmpNode.getFarther();
}while(tmpNode != null);
}else
{
System.out.println("Couldn't find the path!");
}
return tmpLink;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
char[][] map ={
{'Y', 'N', 'z', 'y', 'x', 'w', 'v', 'N', 'N', 'N'},
{'Y', 'N', '1', 'N', 'N', 'N', 'u', 't', 'N', 'N'},
{'N', '1', '2', '1', '1', '1', 'N', 's', 'N', 'N'},
{'N', 'N', '1', 'N', '9', 'N', 'q', 'r', 'N', 'N'},
{'N', 'N', '1', 'N', 'n', 'o', 'p', 'N', 'N', 'N'},
{'N', '4', '5', '6', 'm', 'N', 'N', 'N', 'N', 'N'},
{'N', '3', 'N', '5', 'l', 'k', 'j', 'N', 'N', 'N'},
{'N', 'N', '3', '4', 'N', 'd', 'i', 'd', 'N', 'N'},
{'N', '1', 'N', 'N', '1', 'N', 'h', 'N', 'N', 'N'},
{'N', '1', 'N', 'N', '1', 'N', 'g', 'N', 'N', 'N'},
{'N', 'a', 'b', 'c', 'd', 'e', 'f', 'N', 'N', 'N'}
};
/*map[x][y]
*如上所示：maxY=10 maxX=11 横的代表maxY,竖的代表maxX 可以自己替换
*地图的读取是
*for(i=1;i行的最大值;i++)
* for(j=1;j列的最大值;j++)
* map[i][j] = 地图[i][j]
*/
Link bestPath = new Link();
/*startNode.setFarther(null);
startNode.setPos(21);
startNode.setStep(0);
//endNode.setFarther(startNode);
endNode.setPos(79);
//endNode.setStep(0);*/
FindBestPath path = new FindBestPath(map, 11, 10, 10, 1, 0, 2);
//FindBestPath path = new FindBestPath(map, 11, 10, startNode, endNode);
bestPath = path.getBestPath();
//bestPath.printLink();
}
}
public class Node {
private int step;//从入口到该节点经历的步数
private int pos;//位置
private Node farther;//上一个结点
private int judgeNum;
public Node() {
}
public void setStep(int setStep){
this.step = setStep;
}
public int getStep(){
return this.step;
}
public void setPos(int setPos){
this.pos = setPos;
}
public int getPos(){
return this.pos;
}
public void setFarther(Node setNode){
this.farther = setNode;;
}
public Node getFarther(){
return this.farther;
}
public void setJudgeNum (int setInt){
this.judgeNum = setInt;;
}
public int getJudgeNum(){
return this.judgeNum;
}
}
java 最短路径算法 如何实现有向 任意两点的最短路径
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点
代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain copy
public class Node {
private String name;
private MapNode,Integer child=new HashMapNode,Integer();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public MapNode, Integer getChild() {
return child;
}
public void setChild(MapNode, Integer child) {
this.child = child;
}
}
MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain copy
public class MapBuilder {
public Node build(SetNode open, SetNode close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
图的结构如下图所示：
Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain copy
public class Dijkstra {
SetNode open=new HashSetNode();
SetNode close=new HashSetNode();
MapString,Integer path=new HashMapString,Integer();//封装路径距离
MapString,String pathInfo=new HashMapString,String();//封装路径信息
public Node init(){
//初始路径,因没有A-E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A-B");
path.put("C", 1);
pathInfo.put("C", "A-C");
path.put("D", 4);
pathInfo.put("D", "A-D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A-F");
path.put("G", 5);
pathInfo.put("G", "A-G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
MapNode,Integer childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"-"+child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
SetMap.EntryString, String pathInfos=pathInfo.entrySet();
for(Map.EntryString, String pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
MapNode,Integer childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distanceminDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}
Main用于测试Dijkstra对象
[java] view plain copy
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}
求java实现矩阵图上任意两点的最短路径源码
我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。
代码欣赏：
public static int step = 1;
public static StringBuffer printStep = new StringBuffer();
public static int[][] 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 } };
public static void main(String[] args) {
int i, 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(" 0 1 2 3 4 5 6 7 8 9 10");
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());
}
public static boolean way(int x, int y){
if(maze[8][9] == 2)//代表递归终止条件（也就是当走出出口时标记为 2）
return true;
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 + "n");
step++;
return true;
}else if(way(x + 1, y - 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else if(way(x + 1 , y)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else if(way(x + 1, y + 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else if(way(x, y + 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else if(way(x - 1, y + 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else if(way(x - 1, y)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else if(way(x - 1, y - 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "n");
step++;
return true;
}else{
maze[y][x] = 3;
return false;
}
}else
return false;
}
}
复制代码前需要楼主自己创建个 类
Sample.way(1, 1);这句代码是我的类的静态调用，改下XXXXX.way(1, 1);
XXXXX代表你创建的类。
下面是这个程序运行后的截图