Dijkstra算法（迪杰斯特拉算法）用来解决单源最短路问题

如果边权出现负数，用SPFA 算法

可以用STL的优先队列priority_queue来优化

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]; 
			}
		} 
	} 
}

邻接矩阵版

  • 适合点数<=1000的情况 
int n;G[maxn][maxn];
int d[maxn];
bool vis[maxn]={
   false};

void Dijkstra(int s){
    //s为起点 
	fill(d,d+maxn,INF);
	d[s]=0;//起点s到达自身的距离为0 
	for(int i=0;i<n;i++){
   
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
   
			if(vis[j]==false&&d[j]<MIN){
   
				u=j;
				MIN=d[j];
			}
		}
		//找不到小于INF的d[u],说明剩下的顶点和起点s不连通 
		if(u==-1) return ;
		vis[u]=true;
		for(int v=0;v<n;v++){
   
			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v])
			d[v]=d[u]+G[u][v];
		}
	}
	
}

邻接表版：

struct Node{
   
	int v,dis;//v为边的目标顶点，dis为边权 
};
vector<Node> Adj[maxn];
int n;
int d[maxn];
bool vis[maxn]={
   false};

void Dijkstra(int s){
   
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
   
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
   
			if(vis[j]==false&&d[j]<MIN){
   
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1) return ;
		vis[u]=true;
		for(int j=0;j<Adj[u].size();j++){
   
			int v=Adj[u][j].v;
			if(vis[v]==false&&d[u]+Adj[u][j].dis<d[v]){
   
				d[v]=d[u]+Adj[u][j].dis;
			}
		}
	}
}

最短路径：

设置pre[],令pre[v]表示从起点s到顶点v的最短路径上v的前一个顶点（即前驱结点）

在if内加一行

if(v未被访问&&以u为中介点可以使起点s到顶点v的最短距离d[v]更优){
   
	优化d[v];
	令v的前驱为u; 
} 


for(int v=0; v<n; v++) {
   
	if(vis[v]==false&&G[u][v]!=INF
	        &&d[u]+G[u][v]<d[v]){
   
	    d[v]=d[u]+G[u][v];
		pre[v]=u;//记录v的前驱顶点是u 
	}	
}

第二标尺

  • ①给每条边增加一个边权（花费最小）
  • ②给每个点增加一个点权（物资最大）
  • ③直接问多少条最短路径

①给每条边增加一个边权（花费最小）

for(int v=0; v<n; v++) {
   
	if(vis[v]==false&&G[u][v]!=INF){
   
		if(d[u]+G[u][v]<d[v]){
   
			d[v]=d[u]+G[u][v];
			c[v]=c[u]+cost[u][v];
		}else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]<c[v]){
   
			c[v]=c[u]+cost[u][v];
		}
	}	
}

②给每个点增加一个点权（物资最大）

for(int v=0; v<n; v++) {
   
	if(vis[v]==false&&G[u][v]!=INF){
   
		if(d[u]+G[u][v]<d[v]){
   
			d[v]=d[u]+G[u][v];
			w[v]=w[u]+weight[v];
		}else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
   
			w[v]=w[u]+weight[v];
		}
	}	
}

③直接问多少条最短路径

for(int v=0; v<n; v++) {
   
	if(vis[v]==false&&G[u][v]!=INF){
   
		if(d[u]+G[u][v]<d[v]){
   
			d[v]=d[u]+G[u][v];
			num[v]=num[u];
		}else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
   
			num[v]+=num[u];
		}
	}	
}

题目链接：

1003 Emergency (25分)