算法设计与分析：（分支限界法--单源最短路径）

单源最短路径

（1）问题描述：
如图所示：单源最短路径问题中，每一边都有一个非负边权，要求图G的从源点到顶点S的到目标顶点t之间的最短路径

（2）活结点队列中使用极小堆存储，优先级是结点所对应的当前路径长。取出堆中的最小结点后，如果当前结点 i 到结点 j 有边可达，且从源点出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该结点加入到队列中。
然后就是利用控制关系进行剪枝，如果在解空间树种两条路径到达图中的一个顶点，而解空间树种A点所经过的长度小于B，则把B以及它的子树剪去。

程序代码

package exam1;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class BBShortest {
	static class HeapNode implements Comparable
	{
		int id;//
		float length;//
		public HeapNode(int ii,float LL) {
		id= ii;
		length=LL;
		}
		public int compareTo (Object x)
		{
			float xl=((HeapNode)x).length;
			if(length<xl) return -1;
			if(length==xl) return 0;
			return 1;
			
		}
	}
	public static void shortest(float [][]a,int v,float[]dist,int[]p)
	{
		//dist[j]保存从原点到定点j的距离
		int n=p.length -1;
		LinkedList<HeapNode>nodes=new LinkedList<HeapNode>();
		HeapNode enode=new HeapNode(v,0);
		for(int j=1;j<=n;j++) {
			dist[j]=Float.MAX_VALUE;
		}
		while(true) {//搜索问题解空间
		for(int j=1;j<=n;j++)
		{
			if(a[enode.id][j]!=-1&&enode.length +a[enode.id][j]<dist[j]) {
				dist[j]=enode.length +a[enode.id ][j];
				p[j]=enode.id ;
				HeapNode e=new HeapNode(j,dist[j]);
				nodes.add(e);
				Collections.sort(nodes);
			}
			
		}
		if(nodes.isEmpty()) 
			break;
			else {
				enode=(HeapNode)nodes.poll();
			}
	
		}
		for(int i=2;i<=n;i++) {
			System.out .println(i+"节点的最短距离是："+dist[i]+"; 前驱节点是："+p[i]);
		}
	}

此程序设计参考了《算法设计与分析》里第六章节中的分支限界法，算法开始创建一个最小堆，用于表示活结点优先队列。堆中每个节点的length值是优先队列的优先级。接着算法将源顶点v化为当前扩展节点。