最小成本路径java代码 最小成本路径定义

网络通信问题，用java代码编写关于路由最佳路径选择的程序，图片如下，给报酬也行，跪谢。

你那个文字我看不懂，路由器的路由算法其实就两类：1、距离矢量算法（如RIP协议），2、链路状态协议（如OSPF协议）。路由器不一定按最短路径转发（如OSPF协议），还要看他的路径开销等参数。如果你不考虑其他因素，仅考虑最短路径，可以用Dijistra算法写。

创新互联公司主营赣州网站建设的网络公司,主营网站建设方案,重庆APP开发公司,赣州h5微信小程序开发搭建,赣州网站营销推广欢迎赣州等地区企业咨询

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实现的

有什么无权无向图的最短路径算法比较好

带权图也分有向和无向两种，基本的算法可以看看书咯。 带权的无向图的最短路径又叫最小生成树，Prim算法和Kruskal算法； 带权的有向图的最短路径算法有迪杰斯特拉算法和佛洛依德算法；

String[] s={"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};

System.out.print("请输入数字（1-12）：");

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

String str=br.readLine();

int m=Integer.parseInt(str);

if (m=0||m=13)

{

用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;

}

}