java 求最短路径

Question

求从A点到G点的最短路径，及所用值。我现在只能从图上来看，按规律来查找，但我不知道怎样用代码来显示， 希望哪们大侠能帮俺看看。
在些谢过了。

Answer 1

初始化一个二维数组，这个问题你可以看成从每一列选出一个不为-1，不为0的值，然后所有选出值求和，可以利用一个map，key存储走过的路径，value存储求到的和。最后排序map就能得到最小路径了

Answer 2

A星算法是啥不了解，我只会我想得到=。=...补充下选值的时候只能选半边，如可以设横坐标i要<=纵坐标j之类的

Answer 3

难得上一次，帮你一回，A星代码package com.xiruo.astar;/**
 * @author xjiang
 * 
 */
public class AStar {
private Square[][] squares; public static final byte WALL = 0x1, BLANK = 0x0; public static final byte WALL_MASK = (byte) 0xf; public static final byte OPEN_MASK = (byte) 0x80; public static final byte CLOSED_MASK = (byte) 0x40; private byte[][] map; private Square lStart; private Square lEnd; private static final byte ORTHOGONAL_COST = 1; byte height; byte width; // Binary Heap
public Square[] heapTree; public int heapSize; boolean first = true; void updateMap(byte[][] mapMatrix) {
if (map != null) {
map = null;
releaseFind();
} else {
lStart = new Square((byte) 0, (byte) 0, (byte) 0, (byte) 0);
lEnd = new Square((byte) 0, (byte) 0, (byte) 0, (byte) 0); heapTree = new Square[height * width + 1];
squares = new Square[height][width];
}
map = mapMatrix;
} public void releaseFind() {
int i, j;
for (i = 0; i < height; i++) {
for (j = 0; j < width; j++) {
squares[i][j] = null;
}
} for (i = 0; i < heapTree.length; i++) {
heapTree[i] = null;
}
} public Square findPath(byte sy, byte sx, byte ey, byte ex, boolean canfly) {
lStart.X = sx;
lStart.Y = sy;
lEnd.X = ex;
lEnd.Y = ey;
if (canfly) {
Square sqr, last;
last = lStart;
int sign;
if (ex != sx) {
sign = (ex - sx) / Math.abs(ex - sx);
for (byte i = (byte) (sx + sign); i != ex; i += sign) {
sqr = new Square(sy, i, (byte) 0, (byte) 0);
sqr.parent = last;
last = sqr;
}
}
if (ey != sy) {
sign = (ey - sy) / Math.abs(ey - sy);
for (byte i = (byte) (sy); i != ey; i += sign) {
sqr = new Square(i, ex, (byte) 0, (byte) 0);
sqr.parent = last;
last = sqr;
}
}
lEnd.parent = last;
return lEnd;
} byte height = this.height;
byte width = this.width; int i, j;
for (i = 0; i < height; i++) {
for (j = 0; j < width; j++) {
map[i][j] &= WALL_MASK;
}
}
heapSize = 0; openListInsert(this.lStart.Y, this.lStart.X, (byte) 0, null);
Square current = null; byte tY = 0, tX = 0, tG = 0, tmpG; while (heapSize != 0) {
// 取出open表中第一个
current = openListRemove(); // 到达终点!
if (current.Y == this.lEnd.Y && current.X == this.lEnd.X) {
return current;
} byte cY = current.Y;
byte cX = current.X; fl: for (i = 0; i < 4; i++) {
switch (i) {
case 0: // 上
tY = (byte) (cY - 1);
if (tY < 0)
continue fl;
tX = cX;
tG = ORTHOGONAL_COST;
break;
case 1: // 左
tX = (byte) (cX - 1);
if (tX < 0)
continue fl;
tY = cY;
tG = ORTHOGONAL_COST;
break;
case 2: // 右
tX = (byte) (cX + 1);
if (tX >= width)
continue fl;
tY = cY;
tG = ORTHOGONAL_COST;
break;
case 3: // 下
tY = (byte) (cY + 1);
if (tY >= height)
continue fl;
tX = cX;
tG = ORTHOGONAL_COST;
break;
default:
break;
} if ((this.map[tY][tX] & WALL_MASK) != WALL
&& (this.map[tY][tX] & CLOSED_MASK) == 0) {
if ((this.map[tY][tX] & OPEN_MASK) == 0) {
openListInsert(tY, tX, (byte) (current.g + tG), current);
} else {
tmpG = (byte) (current.g + tG);
if (this.squares[tY][tX].g > tmpG) { this.squares[tY][tX].setG(tmpG);
this.squares[tY][tX].parent = current;
heapPercolateUp(squares[tY][tX].position);
}
}
}
}
this.map[current.Y][current.X] = CLOSED_MASK;
}
return null;
} private byte calculateH(byte y, byte x) {
return (byte) (ORTHOGONAL_COST * (Math.abs(this.lEnd.Y - y) + Math
.abs(this.lEnd.X - x)));
} public void openListInsert(byte tY, byte tX, byte g, Square parent) {
this.squares[tY][tX] = new Square(tY, tX, g, calculateH(tY, tX));
this.squares[tY][tX].parent = parent;
heapInsert(this.squares[tY][tX]);
this.map[tY][tX] = OPEN_MASK;
} public Square openListRemove() {
Square temp = heapDeleteMin();
this.map[temp.Y][temp.X] = OPEN_MASK;
this.squares[temp.Y][temp.X] = null;
return temp;
} // Binary Heap
public void heapPercolateUp(int position) {
if (position <= this.heapSize) {
while (position > 1) {
if (this.heapTree[position].f < this.heapTree[position / 2].f) {
Square temp = this.heapTree[position];
this.heapTree[position / 2].position = position;
this.heapTree[position] = this.heapTree[position / 2];
temp.position = position / 2;
this.heapTree[position / 2] = temp;
position = position / 2;
} else
return;
}
}
} public boolean heapInsert(Square element) {
if (this.heapSize == heapTree.length - 1 || element == null) {
return false;
} this.heapSize++;
int hole = this.heapSize; while (hole > 1 && element.f < this.heapTree[hole / 2].f) {
this.heapTree[hole / 2].position = hole;
this.heapTree[hole] = this.heapTree[hole / 2];
hole = hole / 2;
} this.heapTree[hole] = element;
this.heapTree[hole].position = hole; return true;
} public Square heapDeleteMin() {
if (this.heapSize == 0) {
return null;
} Square smallest = this.heapTree[1];
this.heapTree[this.heapSize].position = 1;
this.heapTree[1] = this.heapTree[this.heapSize];
this.heapTree[this.heapSize] = null;
this.heapSize--; int current = 1;
int child;
while (2 * current <= this.heapSize) {
child = 2 * current; if (child != this.heapSize
&& this.heapTree[child].f > this.heapTree[child + 1].f) {
child++;
} if (this.heapTree[current].f > this.heapTree[child].f) {
Square temp = this.heapTree[current];
this.heapTree[child].position = current;
this.heapTree[current] = this.heapTree[child];
temp.position = child;
this.heapTree[child] = temp;
} else {
break;
}
current = child;
} return smallest;
}}class Square {
public byte f; public byte g; public byte h; public int position; // heap position public byte Y; public byte X; public Square parent; public Square(byte y, byte x, byte g, byte h) {
this.Y = y;
this.X = x; if (!(g == 0 && h == 0)) {
this.g = g;
this.h = h;
this.f = (byte) (this.g + this.h);
}
} public void setG(byte g) {
this.g = g;
this.f = (byte) (this.g + this.h);
}
}

Answer 4

这个链接
http://www.tech-q.cn/thread-10091-1-1.html

Answer 5

我查到的规律是从A点到C点的时候，就可以做判断了， 每三个点如果有相交的地方那么就可以做判断， 如：AB1C2 与 AB2C2  这样C2点我就可以认定A点到C2点的最短距离是 AB1C2； AB1C1它没有相交的点就不判断，只把AB1+B1C1的和； AB2C3 与 AB1C3 它们也有相交点那么我也可以判断 A 点到 C3点的最短路径是 AB2C3； 依次类推， 每一个大的分区(指如：C1 C2 C3 C4) 有多少个点，我算出来它就只能那几个值。我的思路就是这样的

Answer 6

求最短路径是有算法的。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
/**
 * 定义简单图,为最短路径算法准备
 * @author root
 *
 */
public class SimplGraph {
 
    /**
     * 节点值
     */
    public int key;
    /**
     * 相邻节点集合
     */
    public List<Integer> nearNode;
    /**
     * 两节点之间的权重(距离)
     */
    public Map<String,Integer> weight;
    /**
     * 初始化参数
     * @param key
     */
    public SimplGraph(int key){
        this.key = key;
        nearNode = new ArrayList<Integer>();
        weight = new HashMap<String,Integer>();
    }
    /**
     * 添加邻节点
     * 张磊
     *2007-6-23
     *@param node
     *@param lengh
     */
    public void addNode(int node,int lengh){
        //加入邻节点中
        nearNode.add(node);
        //记录类节点和node 节点的权重
        weight.put(Integer.toString(node), lengh);
    }
}
接下来是最短路径基本算法的实现类
 
package graph;
 
import java.util.Iterator;
 
/**
 * 最短路径算法
 * @author root
 *
 */
public class Dijkstra {
 
    SimplGraph[] total;
    /**
     * 初始化数据
     *
     */
    public Dijkstra(){
        total = new SimplGraph[6];
        //设置一个图
        int a = 0,b = 1,c = 2,d = 3,e = 4,f = 5 ;
        SimplGraph Sa = new SimplGraph(0);
        SimplGraph Sb = new SimplGraph(9999);
        SimplGraph Sc = new SimplGraph(9999);
        SimplGraph Sd = new SimplGraph(9999);
        SimplGraph Se = new SimplGraph(9999);
        SimplGraph Sf = new SimplGraph(9999);
        //设置每个节点的邻节点及权值
        Sa.addNode(b,1);
        Sa.addNode(c,4);
        Sa.addNode(d,7);
       
        Sb.addNode(a,1);
        Sb.addNode(c,1);
        Sb.addNode(e,3);
       
        Sc.addNode(a,4);
        Sc.addNode(b,1);
        Sc.addNode(d,3);
        Sc.addNode(f,6);
       
        Sd.addNode(a,7);
        Sd.addNode(c,3);
        Sd.addNode(f,9);
       
        Se.addNode(b,3);
        Se.addNode(f,5);
       
        Sf.addNode(c,6);
        Sf.addNode(d,9);
        Sf.addNode(e,5);
       
        //设置每个节点的索引
        total[a] = Sa;
        total[b] = Sb;
        total[c] = Sc;
        total[d] = Sd;
        total[e] = Se;
        total[f] = Sf;
    }
   
    /**
     * 最短路径计算(基本算法)
     * 张磊
     *2007-6-22
     */
    public void minPath(){
        for (int i = 0; i < total.length; i++) {
            Iterator it = total[i].nearNode.iterator();
            while(it.hasNext()){
                //得到节点的数字索引
                int node = (Integer)it.next();
                //通过索引得到节点的类
                SimplGraph sg = total[node];
                //对此节点进行最短路径计算
                if(sg.key>total[i].key+total[i].weight.get(Integer.toString(node)))
                    sg.key = total[i].key+total[i].weight.get(Integer.toString(node));
            }
        }
    }
   
    public static void main(String[] args){
        Dijkstra d = new Dijkstra();
        d.minPath();
        SimplGraph[] s = d.total;
        for (int i = 0; i < s.length; i++) {
            System.out.println("节点 "+i);
            System.out.println("最短路径为 "+s[i].key);
        }
    }
}看原理的话，看这篇文章http://www.5igis.com/algorithm/shortpath.htm（我的操作系统书上有，不过太多了，我就找了一篇百度置顶的文章，要是看不懂我就把书上的给你打出来）

Answer 7

A *
http://blog.csdn.net/dracularking/archive/2008/06/04/2510036.aspx

Answer 8

楼主这样想
min(A,G) =  Min (min(A,F1) + W(F1,G), min(A,F2) + W(F2,G));
再把这个递归改成递推
就成动态规划了