/**
?*?Name:Dijstra算法，基于鄰接表
?*?Author:楊寅
?*?Date:2009/03/16
?*/
package?dijkstra;

import?java.io.BufferedReader;
import?java.io.InputStreamReader;
import?java.util.linkedList;
import?java.util.ListIterator;

import?gdatastructure.Graph;

public?class?Gdijkstra?{
	
	int?dvalue[];
	int?shortest[];
	int?source?=?0;
	
	private?Graph?mygraph;
	
	public?Gdijkstra（Graph?mygraph）{
		this.mygraph?=?mygraph;
		dvalue?=?new?int[mygraph.size（）?+?1];
		shortest?=?new?int[mygraph.size（）?+?1];
	}
	//用戶交互，提示用戶輸入源點
	public?void?userInterface（）
	{
		System.out.println（“/***?The?Dijkstra?Algorithm?***/“）;
		System.out.println（“Input?your?source?node:“）;
		System.out.print（“$“）;
		BufferedReader?in?=	new?BufferedReader（new?InputStreamReader（?System.in））;
		try{
			this.source?=?Integer.parseInt（in.readLine（）.trim（））;
		}catch（Exception?e）
		{
			
		}
		runDijkstra（）;
		showResults（）;
	}
	private?void?initializeSingleSource（）
	{
		for（int?i?=?1;?i?<=?mygraph.size（）;?i++）
		{
			dvalue[i]?=?-1;?//?-1?is?the?maximum?value
			shortest[i]?=?0;
		}
		dvalue[source]?=?0;
	}
	//松弛算法
	private?void?relax（int?u?int?v?int?w）
	{
		int?edgevalue?=?mygraph.getEdgeValue（u?v）;
		if（dvalue[v]?==?-1?||?dvalue[v]?>?dvalue[u]?+?edgevalue）
		{
			dvalue[v]?=?dvalue[u]?+?edgevalue;
			shortest[v]?=?u;
		}
	}
	//運行Dijkstra算法
	public?void?runDijkstra（）
	{
		//初始化松弛參數
		this.source?=?source;
		initializeSingleSource（）;
		//初始化結點集合S和Q
		linkedList?S?=?new?linkedList（）;
		linkedList?Q?=?new?linkedList（）;
		for（int?i?=?1;?i?<=?mygraph.size（）;?i++）
			Q.add（i）;
		while（Q.size（）?!=?0）
		{
			ListIterator?iterator1?=?Q.listIterator（）;
			ListIterator?iterator2?=?null;
			int?minvalue?=?-1;
			int?minpos?=?-1;
			while（iterator1.hasNext（））
			{
				int?curpos?=?iterator1.next（）;
				if（（minvalue?==?-1?||?dvalue[curpos]?				{
					minvalue?=?dvalue[curpos];
					minpos?=?curpos;
				}
			}
			Q.remove（Q.indexOf（new?Integer（minpos）））;
			S.add（minpos）;
			
			iterator2?=?mygraph.getAllNeighbours（minpos）.listIterator（）;
			while（iterator2.hasNext（））
			{
				int?pos?=?iterator2.next（）;
				relax（minpos?pos?mygraph.getEdgeValue（minpos?pos））;
			}
		}
	}
	//遞歸法打印最短路徑
	private?void?printfPath（int?source?int?dest）
	{
		if（dest?==?source）
			System.out.print（source）;
		else
		{
			printfPath（source?shortest[dest]）;
			System.out.print（“->“?+?dest）;
		}
	}
	//打印結果
	public?void?showResults（）
	{
		System.out.println（“/***?The?Dijkstra?Results?source?point?is?“?+?source+?“?***/“）;
		for（int?i?=?1;?i?<=?mygraph.size（）;?i++）
		{
			if（dvalue[i]?!=?-1?&&?i?!=?source）
			{
				System.out.println（“*******************“）;
				System.out.println（“To?node?[“?+?i?+?“]“）;
				System.out.println（“Minimum?path?length:?“?+?dvalue[i]）;
				printfPath（source?i）;
				System.out.println（““）;
				
			}
		}

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

?????文件????????257??2009-03-16?15:27??GraphAlgorithm\.classpath

?????文件????????390??2009-03-15?17:34??GraphAlgorithm\.project

?????文件???????3818??2009-03-17?11:15??GraphAlgorithm\bin\dijkstra\Gdijkstra.class

?????文件???????2607??2009-03-17?17:01??GraphAlgorithm\bin\gconnectivity\StrongConnectivity.class

?????文件???????1111??2009-03-17?11:22??GraphAlgorithm\bin\gdatastructure\AutoBuildGraph.class

?????文件???????1004??2009-03-16?22:10??GraphAlgorithm\bin\gdatastructure\Color.class

?????文件???????4049??2009-03-17?11:29??GraphAlgorithm\bin\gdatastructure\Graph.class

?????文件???????1199??2009-03-17?11:20??GraphAlgorithm\bin\gdatastructure\link.class

?????文件???????1261??2009-03-17?11:20??GraphAlgorithm\bin\gdatastructure\Vertex.class

?????文件????????734??2009-03-17?11:20??GraphAlgorithm\bin\gdatastructure\VNode.class

?????文件????????728??2009-03-17?16:39??GraphAlgorithm\bin\packagefortest\Main.class

?????文件???????1873??2009-03-17?17:01??GraphAlgorithm\bin\tool\DFSBasic.class

?????文件???????2532??2009-03-17?17:17??GraphAlgorithm\bin\tool\DFSSuc1.class

?????文件???????3141??2009-03-17?11:15??GraphAlgorithm\src\dijkstra\Gdijkstra.java

?????文件???????1641??2009-03-17?17:01??GraphAlgorithm\src\gconnectivity\StrongConnectivity.java

?????文件???????1468??2009-03-17?11:22??GraphAlgorithm\src\gdatastructure\AutoBuildGraph.java

?????文件?????????72??2009-03-16?22:08??GraphAlgorithm\src\gdatastructure\Color.java

?????文件???????3442??2009-03-17?11:29??GraphAlgorithm\src\gdatastructure\Graph.java

?????文件???????1042??2009-03-17?11:20??GraphAlgorithm\src\gdatastructure\link.java

?????文件????????845??2009-03-17?11:20??GraphAlgorithm\src\gdatastructure\Vertex.java

?????文件????????450??2009-03-17?11:20??GraphAlgorithm\src\gdatastructure\VNode.java

?????文件???????1472??2009-03-17?16:39??GraphAlgorithm\src\packagefortest\Main.java

?????文件???????1327??2009-03-17?17:01??GraphAlgorithm\src\tool\DFSBasic.java

?????文件???????1879??2009-03-17?17:17??GraphAlgorithm\src\tool\DFSSuc1.java

?????文件????????329??2009-03-17?17:30??GraphAlgorithm\修改記錄.txt

?????文件??????34816??2009-04-15?22:23??GraphAlgorithm\模塊簡要說明.doc

?????目錄??????????0??2009-03-16?22:10??GraphAlgorithm\bin\dijkstra

?????目錄??????????0??2009-03-16?22:10??GraphAlgorithm\bin\gconnectivity

?????目錄??????????0??2009-03-17?10:35??GraphAlgorithm\bin\gdatastructure

?????目錄??????????0??2009-03-17?11:21??GraphAlgorithm\bin\packagefortest

............此處省略12個文件信息