Dijkstra算法最短路徑----按路徑長度遞增的次序産生最短路徑

一、最短路徑

最短路徑問題（Shortest Path）是指從在帶權圖的某一頂點（稱為源點）出發，找到一條通往另一頂點（稱為終點）的最短路徑。

二、Dijkstra算法

- 基本思想

（1）把圖中的所有頂點分為兩組，一組為已确定最短路徑的頂點；一組為尚未确定最短路徑的頂點。

（2）按路徑長度遞增的順序逐個把第二組的長度加到第一組中去，直到源點出發到達的所有頂點中全部包含至第一組。

• 具體做法

  （1）最開始第一組頂點隻包含頂點v0,第二組包含其他所有頂點。

  （2）确定初始值，v0對應的距離為0，第二組中各頂點若存在邊<v0,vi>或者(v0,vi),則vi的距離為這條邊的權值，若不存在則為無窮大。

  （3）每次從第二組的頂點中選一個權值最小的頂點vu加入到第一組中，并及時對第二組中的距離值做修正。

  （4）循環進行，直到沒有頂點可加入到第一組中。

• 設計思路

  （1）引入一維數組S[i]來記錄頂點vi是否已求得最短路徑，S[i]==false表示未求得最短路徑，S[i]==true表示已求得最短路徑。

  （2）引入一維數組dist[j]記錄目前求出的源點v0到頂點vj的最短路徑距離。

  （3）引入一維數組Path[i]記錄從源點v0到各點vi的最短路徑上vi的直接前驅結點下标；若v0到vi無路徑，則Path[i]==0.

Dijkstra最短路徑///
template<class T, class W>
void ShortestPath(Graph<T, W>& G, int v, W dist[], int path[])
{
	//Graph是一個帶權有向圖，建立一個數組dist[j]（0<=j<n）是目前求到的從頂點v到頂點j的最短路徑長度，用數組path存放求到的n-1條最短路徑
	int n = G.NumberOfVertices();
	bool *S = new bool[n];   //最短路徑頂點集
	int i, j, k, u;
	W w, min;
	for (i = 0; i < n; i++)       //數組初始化
	{
		dist[i] = G.getWeight(v, i);
		S[i] = false;
		if (i != v && dist[i] < MaxWeight)
			path[i] = v;
		else
		{
			path[i] = -1;
		}
	}
	S[v] = true;
	dist[v] = 0;   //頂點v加入頂點集合
	for (i = 0; i < n - 1; i++)   //選不在S中的最短路徑頂點u
	{
		min = MaxWeight;
		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 < MaxWeight && dist[u] + w < dist[k])
			{   //頂點k未加入S，且繞過u可縮短路徑
				dist[k] = dist[u] + w;
				path[k] = u;   //修改到k的最短路徑
			}

		}
	}