本文目录一览：
用java求最短路径问题，求源程序
import java.util.Vector;
public class Link {
private Vector link = new Vector();
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);
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);
for (int i = 1; i < this.link.size(); i++) {
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;
public FindBestPath(char[][] setMap, int setX, int setY, int sX, int sY, int eX, int eY) {
this.map = setMap;
this.maxY = setX - 1;
this.maxX = setY - 1;
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;
this.endY = eY;
}
public int posToNum(int x, int y) {
return (x + y * (this.maxY + 1));
}
public int numToX(int num) {
return (num % (this.maxY + 1));
}
public int numToY(int num) {
return (int) (num / (this.maxY + 1));
}
public boolean checkVal(int x, int y) {
if (this.map[x][y] == 'N')
return false;
else
return true;
}
public int judge(Node nowNode) {
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
int distance = Math.abs((nowX - this.endX)) + Math.abs((nowY - this.endY));
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()) {
bestNode = openLink.getBestNode();
if (bestNode.getPos() == this.endNode.getPos()) {
path = makePath(bestNode);
break;
} else {
tmpNode = closeLink.checkNode(getLeft(bestNode));
if (tmpNode != null)
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getRight(bestNode));
if (tmpNode != null)
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getTop(bestNode));
if (tmpNode != null)
openLink.addNode(tmpNode);
tmpNode = closeLink.checkNode(getBottom(bestNode));
if (tmpNode != null)
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;
}
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'}
};
Link bestPath = new Link();
FindBestPath path = new FindBestPath(map, 11, 10, 10, 1, 0, 2);
bestPath = path.getBestPath();
}
}
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表的方式，其采用的是贪心法的算法策略，大概过程如下：
- 声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
- 初始阶段，将初始节点放入close，其他所有节点放入open
- 以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点 代码实例如下： Node对象用于封装节点信息，包括名字和子节点
public class Node {
private String name;
private Map<Node, Integer> child = new HashMap<Node, Integer>();
public Node(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}
MapBuilder用于初始化数据源，返回图的起始节点
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> 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对象用于计算起始节点到所有其他节点的最短路径
public class Dijkstra {
Set<Node> open = new HashSet<Node>();
Set<Node> close = new HashSet<Node>();
Map<String, Integer> path = new HashMap<String, Integer>();
Map<String, String> pathInfo = new HashMap<String, String>();
public Node init() {
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");
Node start = new MapBuilder().build(open, close);
return start;
}
public void computePath(Node start) {
Node nearest = getShortestPath(start);
if (nearest == null) {
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node, Integer> childs = nearest.getChild();
for (Node child : childs.keySet()) {
if (open.contains(child)) {
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() {
Set<Map.Entry<String, String>> pathInfos = pathInfo.entrySet();
for (Map.Entry<String, String> pathInfo : pathInfos) {
System.out.println(pathInfo.getKey() + ":" + pathInfo.getValue());
}
}
private Node getShortestPath(Node node) {
Node res = null;
int minDis = Integer.MAX_VALUE;
Map<Node, Integer> childs = node.getChild();
for (Node child : childs.keySet()) {
if (open.contains(child)) {
int distance = childs.get(child);
if (distance < minDis) {
minDis = distance;
res = child;
}
}
}
return res;
}
}
Main用于测试Dijkstra对象
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},
{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);
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)
return true;
else {
if (maze[y][x] == 0) {
maze[y][x] = 2;
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代表你创建的类。
下面是这个程序运行后的截图
