Dijkstra算法

/*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次。*/