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