第十章 图算法专题

10.4 最短路径

对于给定的图G、起点S和终点T，求出S到T的最短路径

10.4.1 Dijkstra算法

单源最短路问题：给定图G和起点S，得到S到其他每个顶点的最短距离。非负边。

集合S存放已被访问过的顶点，执行n次以下步骤：

• 从集合V-S中选择与起点s距离最短的顶点u，访问u并加入集合S中。
• 另u为中介店，优化起点s到所有u能到达的顶点v（未被访问过的）之间的最短距离。

具体实现

• 集合S：bool vis[]
• 起点s到其他顶点的最短距离：int d[]，初始化时，除d[s]=0外，其余初始化为inf

邻接矩阵实现

#include <cstdio>
#include <algorithm> 	//fill头文件 
using namespace std; 	//使用algorithm头文件的前提 

const int MAXV=1000; 	//最大定点数
const int INF=1e9;

int n,G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV]={false}; 	//初值为false，表示全都未被访问过

void Dijkstra(int s)
{
	fill(d,d+MAXV,INF);
	d[s]=0;
	for(int i=0;i<n;i++) 	//循环n次 
	{
		int u=-1,MIN=INF; 	//MIN表示起点到V-S中顶点u的最小距离 
		for(int j=0;j<n;j++)
		{
			if(vis[j]==false&&d[j]<MIN)
			{
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1)
			return ; 	//剩下的顶点与s不通
		vis[u]=true; 	//访问顶点u
		for(int v=0;i<n;v++)
		{	//v未被访问过，u能到达v，d[v]能被优化 
			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v])
			{
				d[v]=d[u]+G[u][v];
			}
		} 
	}
} 

复杂度：O(V²)
邻接链表实现

变种

无向边：指向相反的有向边
最短路径：前驱结点数组pre[]，pre[v]表示从起点s到顶点v的最短路径上的v的前一个顶点。

for(int v=0;i<n;v++)
{	//v未被访问过，u能到达v，d[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; 	//记录前驱结点
	}
} 

//输出最短路径
void dfs(int s,int v)
{
	if(v==s)
	{
		printf("%d",s);
		return ;
	}
	dfs(s,pre[v]);
	printf("%d",v);	
}

最短路径不止一条：第二标尺
增加一个数组来存放新增的边权或点权或最短路径条数。

1. 每条边再加一个权
   增加一个数组c[]

if(vis[v]==false&&G[u][v]!=INF)
{
	if(d[v]<d[u]+G[u][v])
	{
		d[v]=d[u]+G[u][v];
		c[v]=c[u]+C[u][v];
	}
	else if(d[v]==d[u]+G[u][v]&&c[v]<c[u]+C[u][v]) 	//最短路径相同
	{
		c[v]=c[u]+C[u][v]; 	//看第二标尺是否更优 
	} 		
}

2. 每个点增加一个权

if(vis[v]==false&&G[u][v]!=INF)
{
   if(d[v]<d[u]+G[u][v])
   {
   	d[v]=d[u]+G[u][v];
   	w[v]=w[u]+weight[v];
   }
   else if(d[v]==d[u]+G[u][v]&&w[v]<w[u]+weight[v]) 	//最短路径相同
   {
   	w[v]=w[u]+weight[v]; 	//看第二标尺是否更优 
   } 		
}

3. 问有多少条最短路径

if(vis[v]==false&&G[u][v]!=INF)
{
   if(d[v]<d[u]+G[u][v])
   {
   	d[v]=d[u]+G[u][v];
   	num[v]=num[u];
   }
   else if(d[v]==d[u]+G[u][v]) 	//最短路径相同
   {
   	num[v]+=num[u];
   } 		
}