/*Dijkstra算法偽代碼：//G為圖，一般設成全局變量；數組d為源點到達各點的最短路徑長度，s為起點Dijkstra(G,d[],s){	初始化；	for(循環n次)	{		u = 使d[u]最小的還未被訪問的頂點的標號；		記u已被訪問；		for(從u出發能到達的所有頂點v)		{			if(v未被訪問&&以u為中介點使s到頂點v的最短距離d[v]更優)			{				優化d[v]；				(令u為v的前驅)用于求最短路徑本身			}		}	}}遞歸求最短路徑：void DFS(int s,int v)//s為起點編號，v為當前訪問的頂點編號(從終點開始遞歸){	if(v==s)//如果當前已經到達起點s，則輸出起點并返回	{		PRintf("%d/n",s);		return;	}	DFS(s,pre[v]);//遞歸訪問v的前驅頂點pre[v]	printf("%d/n",v);//從最深處return回來之后，輸出每一層的頂點號}*/#include<cstdio>#include<vector>#include<algorithm>using namespace std;const int MAXV = 1000;//最大頂點數const int INF = 1000000000;//設INF為一個很大的數//鄰接矩陣版int n, G[MAXV][MAXV];//n為頂點數，MAXV為最大頂點數int d[MAXV];//起點到達各點的最短路徑長度bool vis[MAXV] = { false };//標記數組，vis[i]==true表示已被訪問。初值均為falsevoid Dijkstra(int s)//起點{	fill(d, d + MAXV, INF);//fill函數將整個d數組賦為INF(慎用memset)	d[s] = 0;//起點s到達自身的距離為0	for (int i = 0; i < n; i++)//循環n次	{		int u = -1, MIN = INF;//u使d[u]最小，MIN存放該最小的d[u]		for (int j = 0; j < n; j++)//找到未訪問的頂點中d[]最小的		{			if (vis[j] == false && d[j] < MIN)			{				u = j;				MIN = d[j];			}		}		//找不到小于INF的d[u],說明剩下的頂點和起點s不連通		if (u == -1) return;		vis[u] = true;//標記u為已訪問		for (int v = 0; v < n; v++)		{//如果v未被訪問&&u能到達v&&以u為中介點可以使d[v]更優			if (vis[v] == false && G[u][v] != INF&&d[u] + G[u][v] < d[v])			{				d[v] = d[u] + G[u][v];//優化d[v]			}		}	}}//鄰接表版struct Node{	int v, dis;//v為邊的目標頂點，dis為邊權};vector<Node> Adj[MAXV];//圖G，Adj[u]存放從頂點u出發可以到達的所有頂點int n;//n為頂點數，圖G使用鄰接表實現，MAXV為最大頂點數int d[MAXV];//起點到達各點的最短路徑長度bool vis[MAXV] = { false };//標記數組,vis[i]==true表示已訪問。初值均為falsevoid Dijkstra(int s)//s為起點{	fill(d, d + MAXV, INF);//fill函數將整個d數組賦為INF(慎用memeset)	d[s] = 0;//起點s到達自身的距離為0	for (int i = 0; i < n; i++)//循環n次	{		int u = -1, MIN = INF;//u使d[u]最小，MIN存放該最小的d[u]		for (int j = 0; j < n; j++)//找到未訪問的頂點中d[]最小的		{			if (vis[j] == false && d[j] < MIN)			{				u = j;				MIN = d[j];			}		}		//找不到小于INF的d[u]，說明剩下的頂點和起點s不連通		if (u == -1) return;		vis[u] = true;//標記u為已被訪問		//只有下面這個for與鄰接矩陣的寫法不同！??！		for (int j = 0; j < Adj[u].size(); j++)		{			int v = Adj[u][j].v;//通過鄰接表直接獲得u能到達的頂點v			if (vis[v] == false && d[u] + Adj[u][j].dis < d[v])			{//如果v未被訪問&&以u為中介點可以使d[v]更優				d[v] = d[u] + Adj[u][j].dis;//優化d[v]			}		}	}}/*本人總結為：Dijkstra = 找最小u + 以u為中介找所有未被訪問且可達的v，若d[u]加上u到v之間的距離小于d[v]則d[v]=d[u] + DIS(u->v);上述只是一次過程，若有n個點需循環n次。*/