最短路徑算法java代碼（最短路徑算法java代碼是什麼）

本文目錄一覽：

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)){