import?java.util.HashMap;
import?java.util.linkedList;
import?java.util.Queue;

public?class?GraphByMatrix?{
	private?int[]?vertexesArray;//頂點
	Double[][]?edgesMatrix;//存儲路徑時間
	private?boolean[]?visited;//是否訪問過
	private?int?vertexSize?=?0;
	public?boolean?isDirected?=?false;//是否有向
	public?int?maxSize?=?0;
	public?static?final?Double?MAX_VALUE?=?Double.MAX_VALUE;//如果沒有直接連通就初始化為MAX_VALUE
	public?Double[]?dist;//存儲時間
	public?HashMap?vertexQueue;//存儲路徑
	
	public?GraphByMatrix（int?size）{
		init（size）;
	}
	
	private?void?init（int?size）{//初始化
		maxSize?=?size;
		vertexesArray?=?new?int[maxSize];
		visited?=?new?boolean[maxSize];
		edgesMatrix?=?new?Double[maxSize][maxSize];
		for?（int?row?=?0;?row?????????????for?（int?column?=?0;?column?????????????	if（row==column）{
????????????		edgesMatrix[row][column]?=?0.0;
????????????	}
????????????	else{
????????????		edgesMatrix[row][column]?=?MAX_VALUE;
????????????	}
????????????}??
????????}
	}
	
	public?void?addvertex（int?n）{//添加頂點
		vertexesArray[vertexSize]?=?n;
		vertexSize++;
	}
	
	public?void?addEdge（int?startint?endDouble?edge）?throws?Exception{//添加路徑
		int?s?=?getVertexIndex（start）;
		int?e?=?getVertexIndex（end）;
		if（isDirected）{
			edgesMatrix[s][e]?=?edge;
		}
		else{
			edgesMatrix[s][e]?=?edge;
			edgesMatrix[e][s]?=?edge;
		}
	}
	
	public?void?changeType（boolean?isDirected）{//改變類型，默認為無向圖，基本可以不管
		this.isDirected?=?isDirected;
	}
	
	public?void?Dijkstra（int?startint?end）?throws?Exception{//獲取最短路徑和時間
		int?s?=?getVertexIndex（start）;
		int?e?=?getVertexIndex（end）;
		vertexQueue?=?new?HashMap（）;//存儲路徑
		dist?=?new?Double[maxSize];//存儲結果
		
		for（int?i?=?0;i			visited[i]?=?false;
			dist[i]?=?MAX_VALUE;
		}
		
		Queue?queue?=?new?linkedList（）;
		queue.add（s）;
		vertexQueue.put（s?queue）;
		dist[s]?=?0.0;
		visited[s]?=?true;
		
		int?temp?=s;
		Iterator（tempe）;
		
		queue?=?vertexQueue.get（e）;
????????System.out.print（“路徑為:“）;
????????while（!queue.isEmpty（））{
????????	System.out.print（vertexesArray[queue.remove（）]）;
????????}
????????System.out.println（“時間為:“+dist[e]）;
	}
	
	public?void?Iterator（int?tempint?e）{//寬度遍歷
		Queue?queue?=?new?linkedList（）;
		Queue?qVertex?=?new?linkedList（）;
		for（int?i=0;i			//System.out.print（“1“）;
			if（edgesMatrix[temp][i]?!=?MAX_VALUE&&dist[temp]+edgesMatrix[temp][i]				dist[i]?=?dist[temp]+edgesMatrix[temp][i];
				queue?=?new?linkedList（vertexQueue.get（temp））;
				queue.add（i）;
				qVertex.add（i）;
				if（vertexQueue.containsKey（i））{
					vertexQueue.replace（i?queue）;
				}
				else{
					vertexQueue.put（i?queue）;
				}
			}
		}
		while（!qVertex.isEmpty（））{
			temp?=?qVertex.remove（）;
			Iterator（tempe）;
		}
		visited[temp]?=?true;
	}
??
????//獲取頂點值在數組里對應的索引??
?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-06-17?12:08??Dijkstra\
?????文件?????????301??2017-06-17?12:08??Dijkstra\.classpath
?????文件?????????384??2017-06-17?12:08??Dijkstra\.project
?????目錄???????????0??2017-06-17?12:08??Dijkstra\.settings\
?????文件?????????598??2017-06-17?12:08??Dijkstra\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2017-06-17?13:53??Dijkstra\bin\
?????文件????????4073??2017-06-17?16:16??Dijkstra\bin\GraphByMatrix.class
?????文件????????1408??2017-06-17?16:12??Dijkstra\bin\Main.class
?????目錄???????????0??2017-06-17?13:53??Dijkstra\src\
?????文件????????3514??2017-06-17?16:16??Dijkstra\src\GraphByMatrix.java
?????文件?????????908??2017-06-17?16:12??Dijkstra\src\Main.java