dijkstra 最短路徑算法

 Dijkstra(迪傑斯特拉)算法是典型的最短路徑路由算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充，直到擴充到終點為止。 Dijkstra算法 能得出最短路徑的最優解，但由于它周遊計算的節點很多，是以效率低。

　　Dijkstra算法是很有代表性的最短路算法，在很多專業課程中都作為基本内容有詳細的介紹，如資料結構，圖論，運籌學等等。

其基本思想是，設定頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。

初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間隻經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄目前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，将u添加到S中，同時對數組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。

例如，對下圖中的有向圖，應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下表中。

Dijkstra算法的疊代過程：

參考書上的部分代碼

void ShortestPath(Graph<T,E> &G , T v ,E dist[] ,int path[] )  {//G是所給圖，T是頂點的資料類型，E是頂點邊上權值的類型 
	//path是用來存放求到最短路的路徑
	
	int n = G.getNum() ;//先求出圖中頂點的數目，數量為n
	bool *S = new bool[n] ;//開辟一個bool型的集合S
	int  i, j , k ;
	E w ;
	E min ;
	for(i = 0; i<n;i++) { //這個循環的作用是初始化集合S和path數組
		dist[i] =G.getWeight(v,i) ;//存放v和i之間的權值
		S[i] = false ; //點i未通路
		if (i != v && dist[i] <maxValue)
			path[i] = v ;//初始化
		else 
			path[i] = -1 ;
		
	}
	
	S[v] =true ;//v加入頂點集合
	dist[v] = 0 ;
	for( i =0;i<n-1;i++) {
		min = maxValue ;
		int u = v ;
		for(j =0; j < n ;j++) {
			if(S[j] == false && dist[j] <min ) {   u = j ; min =dist[j] ;}
			S[u] =true ; //将頂點u 加入集合S
			for(k=0;k< n ;k++ ) {
				w= G.getWeight(u,k) ;
				if(S[k] == false && w<maxValue && dist[u] +w<dist[k] ) {
					dist[k] = dist[u] +w ;
					path[k] = u ;
				}		
			}
		}
	}
}
           

因為是看着書學的是以思想和代碼也基本和書上一樣了，可以自己敲出來，書上這個算法寫的不錯，值得把玩，

maxValue指的是源點到頂點是沒有邊的，就把權值賦為maxValue。 判斷結束的方法是直到所有的頂點都進入S集合了，就成功，相當于都true了~~