图－最小路径

这里使用的是Dijkstra来计算最短路径。事实上Dijkstra完成时，指定节点到所有节点的最小路径均已求出。

算法简述如下：

准备好两个辅助性数据结构：

1 ParentLength ： 用来记录到当前节点之前的父节点，与到当前节点的最小路径

2 Path： 记录指定节点到所有节点的ParentLength。初始化时，所有的ParentLength的父节点都为指定的起始节点，长度都是INFINITY，代表没有联通，距离无穷大。

Path的关键算法是adjust(from,to,length)，每当发现一条新的，从一个已访问的节点（from）到未访问的节点（to）之间的新路径时，Path则用其更新ParentLength列表，重新计算到那个未访问节点（to）的最新距离：以前到from节点的距离＋新的距离，然后比较它与to节点对应的ParentLength老的距离之间的长度，如果新距离短，则将to节点对应的ParentLength更新为长度为新距离的，父节点为from；以此步骤保证Path总是保持当前遍历状态下，到各个节点的最短路径。

Path的另一个关键算法是getMin，它会返回到所有未访问节点中，最短的路径的那个节点。

图使用邻接矩阵法表示，关于邻接矩阵可参见：Graph 图－邻接表法

Graph.path是最小路径算法，工作方式如下：

    根据指定的起始节点初始化返回值Path对象。

将指定的起始节点标志为已访问。并设置为当前节点。

然后

1 找到当前节点所有联通的未知节点，和到这些路径长度，调用Path.adjust更新Path。

2 步骤 1 结束后，从调用Path.getMin获得到所有未访问节点中，最短的路径的那个节点。标志为访问过，并作为当前节点。

3 重复 步骤 1 步骤 2 n次（n为图中的节点数量），算法结束。

代码中的Path.print()为打印函数，为测试之用。

Path.main()提供简单测试。

 

class ParentLength {	//记载上一个节点与当前最小路径
	private int parent;		//上一个节点
	private int length;		//最小路径长度
	ParentLength(int parent, int length) {
		this.parent = parent;
		this.length = length;
	}

	int parent() {	return parent; }
	int length() {	return length; }
}

class Path {	//存储最小路径
	private ParentLength[] pls;
	private Graph g;	//确定指定位置的节点是否被访问过和打印时使用
	Path(int size, int start, Graph g) { 
		//初始化最小路径数组，将所有最小路径的起点都置为start，并将路径长度置为INFINITY
		pls = new ParentLength[size];	
		for(int i=0; i<size; i++) 
			pls[i] = new ParentLength(start,Graph.INFINITY);
		this.g = g;
	}
	
	//根据新发现的路径调整最小路径
	void adjust(int from, int to, int length) {
		//根据上一个节点的路径，计算出新的路径长度
		int newLength = pls[from].length() != Graph.INFINITY? 
			pls[from].length() + length: length;
		//如果到指定节点的新路径长度小于原来的最小路径，则更新到该节点的最小路径，和其父节点
		if(newLength < pls[to].length()) pls[to] = new ParentLength(from,newLength);
	}

	int getMin() {	//求得到当前所有未访问节点的最近的一个节点
		int pos = 0;
		for(int i=1; i<pls.length; i++)
			if(!g.isVisited(i) && pls[i].length() < pls[pos].length()) pos = i;
		return pos;
	}

	void print() {	//打印
		for(int i=0; i<pls.length; i++) {
			int current = i;	
			System.out.print((pls[current].length() == Graph.INFINITY? "INFINITY": pls[current].length()) + "  " );
			do {
				System.out.print(g.get(current) + " <-- ");
				current = pls[current].parent();	
			} while(current != pls[current].parent());
			System.out.println(g.get(current));
		}
	}
}

class Vertex { //顶点,记载数据value，并记载是否访问过
	private Object value;
	private boolean isVisited;
	Vertex(Object value) {
		this.value = value;
	}

	void visit() { isVisited = true; }
	void clean() {	isVisited = false; }
	boolean isVisited() { return isVisited; }
	Object value() { return value; }
	@Override public String toString() {	return "" + value; }
}

class Graph {
	private Vertex[] vertexs;
	private int[][] adjMat;
	private int length = 0;
	static final int INFINITY = ~(1<<31);	//整数的最大值，表示没有路径

	Graph(int size) {	//初始化
		vertexs = new Vertex[size];
		adjMat = new int[size][size];
		for(int i=0; i<size; i++)	//将邻接矩阵初始化为全部不通
			for(int j=0; j<size; j++)
				adjMat[i][j] = INFINITY;
	}

	void add(Object value) {	//添加顶点
		assert length <= vertexs.length;
		vertexs[length++] = new Vertex(value);
	}

	void connect(int from, int to, int length) {
		adjMat[from][to] = length;	//设置指定节点之间的有向路径
	}

	/**
	 * 在邻接矩阵中，查找指定顶点的未访问过邻居顶点
	 * 如果从从起点到终点的边存在，且没有标志为访问，则返回终点下标。
	 * @param offset 指定开始查找的列
	 * @param index	指定查找的行
	 */
	int findNeighbor(int index,int offset) {
		for(int i=offset; i<length; i++) {
			if(adjMat[index][i] != INFINITY && !vertexs[i].isVisited()) return i;
		}
		return -1;
	}

	Vertex get(int index) {	return vertexs[index];	}

	Path path(int index) {	//最小路径算法
		assert vertexs[index] != null;
		Path result = new Path(length,index,this); //初始化Path
		vertexs[index].visit();	//将其实节点标志为访问过
		for(int n=1; n<length; n++) {	//一共经过n此迭代就可得到最终结果
			int i = 0;
			while((i = findNeighbor(index,i+1)) != -1)	//寻找当前节点的所有为访问邻居
				result.adjust(index, i, adjMat[index][i]);	//根据新路线调整最小路径
			index = result.getMin();	//将当前节点更新为路径表中为访问的最近的那个节点
			vertexs[index].visit();	//将当前节点标志为访问过;
		}
		clean();
		return result;
	}

	boolean isVisited(int index) { return vertexs[index].isVisited(); }

	void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }

	public static void main(String[] args) {
		Graph g = new Graph(20);
		//添加节点
		g.add('a');
		g.add('b');
		g.add('c');
		g.add('d');
		g.add('e');
		//添加有向有权边
		g.connect(0,1,50);
		g.connect(0,3,80);
		g.connect(1,2,60);
		g.connect(1,3,90);
		g.connect(2,4,40);
		g.connect(3,2,20);
		g.connect(3,4,70);
		g.connect(4,1,50);
		Path p = g.path(0);	//获得最小路径
		p.print();	//打印
	}
}

 

评论

3 楼 run_xiao 2008-08-06  

A* 算法？？没听说啊，大多数教科书上都还是Dijkstra吧

2 楼 kldwq2002 2008-07-28  

Great job!

This blog is the best one in javaeye, keep update please.

1 楼 feng_gladys 2008-05-29  

获取最小路径的算法基本都是A* 算法的变体，Dijkstra算法很少用吧