/**
?*?@（#）BBShortest.java
?*
?*
?*?@author?wangwei
?*?@version?1.00?2007/12/19
?*/

public?class?BBShortest?{
????
????public?static?float[][]?a={
		{Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE}
???????	{Float.MAX_VALUE?Float.MAX_VALUE?10???Float.MAX_VALUE?30???100}
???????	{Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?50?Float.MAX_VALUE?Float.MAX_VALUE}
???????	{Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?10}
???????	{Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?20?Float.MAX_VALUE?60}
???????	{Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE?Float.MAX_VALUE}??	???????	
???		};
????public?static?int[]?display?=?new?int[6];
????public??static?float[]?dist?=?new?float[6];
????public?static?int[]?p?=?new?int[6];
???/**
????*?@param?a?//圖G的鄰接矩陣
????*?@param?display?用來打印運算結果
????*?@param?dist?存入v（ij）和最短路徑
????*?@param?p?記錄最短路徑的有頂點信息
????*/
????public?static?void?main?（String[]?args）?{

??	???	??BBShortest?shortest?=?new?BBShortest（）;
??	???	??shortest.shortest（1distp）;
??	???	??shortest.display（5）;
??	???	??
????}

????public?BBShortest（）?{
????}
?	/**
?	?*@author?wangwei
?	?*@category?display（int?n）:顯示頂點v到頂點n的最短路徑的長度，和走法
?	?*/
	public?void?display（int?n）{
?		System.out.println（“到頂點“?+?n?+?“的最短路徑長度是：“?+?dist[n]）;
?		System.out.print（“最短路徑是：“）;
?		display[1]?=?p[n];//把目標點的前驅給display[1]
?		int?i;
?		for（?i?=?2;display[i?-?1]?!=?1?&&?i?<=?5;i++）
?			display[i]?=?p[display[i?-?1]];
?		//display[i++]?=?n;
?		//int?i?=?2;
?		//do{
?		//	display[i]?=?prev[display[i?-?1]];
?		//	i++;
?		//}
?		//while（?!=?1）;
?		
?		for（int?j?=?5;j?>?0;j--）{
?			if（display[j]?!=?0）
?				System.out.print（display[j]?+?“?“）;
?		}
?		System.out.println（n）;
?	}
	
????public?static?void?shortest（int?vfloat[]?distint[]?p）{
????	int?n?=?p.length?-?1;
????	MinHeap?heap?=?new?MinHeap（）;
????	//定義源為初始擴展結點
????	HeapNode?enode?=?new?HeapNode（v0）;
????	for（int?j?=?1;j?<=?n;j++）
????		dist[j]?=?Float.MAX_VALUE;
????	dist[v]?=?0;
????	while（true）{
????		//搜索問題的解空間
????		for（int?j?=?1;j?<=?n;j++）
????			if（a[enode.i][j]?????				enode.length?+?a[enode.i][j]?????					//頂點I到J可達，且滿足控制約束
????					dist[j]?=?enode.length?+?a[enode.i][j];
????					p[j]?=?enode.i;
????					HeapNode?node?=?new?HeapNode（jdist[j]）;
????					//向最小堆中插入活結點優先隊列
????					heap.insert（node）;
????				}
????				if（heap.isEmpty（））
????					break;
????				else?enode?=?（HeapNode）heap.removeMin（）;
????	}
????}
????
????
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????409??2007-12-20?17:28??HeapNode.java

?????文件???????2609??2007-12-20?17:28??MinHeap.java

?????文件???????2794??2007-12-20?17:47??BBShortest.java

-----------?---------??----------?-----??----

?????????????????5812????????????????????3