单源最短路径问题

青旅半醒 2021-09-21 06:28 351阅读 0赞

### 单源最短路径问题 ###

*  概念
 *  Dijkstra算法
 *  最短路径常见问题
 *  Bellman-Ford算法

# 概念 #

> 单源最短路径问题是这样一个问题：在图中给定一个起点，求起点到其它顶点的最短距离。

# Dijkstra算法 #

Dijkstra算法是用来解决边权非负的情况的。它的基本思想是设一个数组d\[n\]用来代表起点到其它顶点的最短距离。初始的时候d\[start\]为0，其它的d\[i\]设为无穷。然后从起点开始遍历整个图，若存在顶点u,使得d\[u\] + G\[u\]\[v\] < d\[v\] 那么就跟新d\[v\]。Dijkstra的实现是通过求出起点到其他所有顶点的最短距离，这样就可得到了起点到给定终点的距离了。  
算法框架如下：

#include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxv = 100; //最大顶点数
    const int INF = 0x3fffffff;
    struct node{ 
    	int v,dis;
    }temp;
    bool vis[maxv]; //标记该顶点是否已经访问
    int d[maxv];
    int pre[maxv]; //记录最短路径 
    int n,m;//顶点数和边数 
    vector<node>Adj[maxv];
    
    void Dijsktra(int s){ 
    	//初始化
    	fill(d,d+maxv,INF);
    	fill(vis,vis+maxv,false);
    	for(int i=1; i<=n; i++){ 
    		pre[i] = i; //顶点i的前驱顶点初始化为其本身 
    	}
    	d[s] = 0; //起点到自己的距离为0
    	for(int i=0; i<n; i++){ 
    		int u = -1,MIN = INF;
    		for(int j=1; 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;
    			int dis = Adj[u][j].dis;
    			if(vis[v]==false && d[u]+dis < d[v]){ 
    				//更新
    				d[v] = d[u] + dis;
    				pre[v] = u; //记录最短路径 
    			}	
    		} 	
    	}
    }
    
    //打印路径
    void dfs(int start,int end ){ 
    	if(start == end){ 
    		printf("%d",end);
    		return;
    	}
    	dfs(start,pre[end]);
    	printf(" %d",end);
    } 
    
    
    int main(){ 
    	int start,end;
    	scanf("%d%d%d%d",&n,&m,&start,&end);
    	for(int i=0; i<m; i++){ 
    		//这里是有向图，顶点编号从1开始 
    		int v;
    		scanf("%d%d%d",&v,&temp.v,&temp.dis);
    		Adj[v].push_back(temp);
    	}
    	Dijsktra(start);
    	//打印最短路径 
    	printf("%d\n",d[end]);
    	//打印路径
    	dfs(start,end);
    	return 0; 
    }

# 最短路径常见问题 #

在求最短路径的时候，经常会遇到其他的额外的问题，就是当最短路径条数不唯一时，有第二个度量：

1.  边权最小（花费最小）  
    这个时候只需要在开始的时候开一个c\[maxv\]数组来记录最小花费，初始的时候c\[s\]为0，其他的c\[i\]均为 INF（这个和求最短路径的数组初始化是一致的），以及cost\[maxv\]\[maxv\]二维数组来记录两个定点之间的花费。并且在d\[v\]改变的地方添加一些代码即可。

if(vis[v]==false ){ 
    	if(d[v] > d[u] + dis){ 
    		//更新最短路径
    	    d[v] = d[u] + dis;
    		pre[v] = u; //记录最短路径
    		c[v] = c[u] + cost[u][v];
    	}else if(d[v] == d[u] + dis){  
    		if(c[v] > c[u] + cost[u][v]){ 
    			c[v] = c[u] + cost[u][v];
    			pre[v] = u;
    		}
    	}	 
    }

1.  点权最大（物质重量）  
    这个时候需要开一个w\[maxv\]来记录起点到其它各个顶点的最大权重，weight\[maxn\]用来记录每一个顶点的权重。并且开始的时候w\[s\] = weight\[s\],其他的w\[i\]均置为0。也是在上面的代码处做一些修改

if(vis[v]==false ){ 
    	if(d[v] > d[u] + dis){ 
    		//更新最短路径
    	    d[v] = d[u] + dis;
    		pre[v] = u; //记录最短路径
    		w[v] = w[u] + weight[v];
    	}else if(d[v] == d[u] + dis){  
    		if(w[v] < w[u] + weight[v]){ 
    			w[v] = w[u] + weight[v];
    			pre[v] = u;
    		}
    	}	 
    }

1.  求最短路径的条数  
    这里需要开一个num\[maxv\]的数组来记录起点到各个顶点最短路径的条数。初始化的时候num\[s\]设置为1，其他的num\[i\]初始化的值为0  
    相关代码如下：

if(vis[v]==false ){ 
    	if(d[v] > d[u] + dis){ 
    		//更新最短路径
    	    d[v] = d[u] + dis;
    		num[v] = num[u];
    	}else if(d[v] == d[u] + dis){  
    		num[v]+=num[u];//累加 
    	}	 
    }

# Bellman-Ford算法 #

BF算法可以用来解决**边权为负**的最短路径问题，同时也能判断出是否存在源点可达的负环

#include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxv = 100;
    const int INF = 0x3fffffff;
    struct node{ 
    	int v,dis;
    };
    vector<node>Adj[maxv];
    int d[maxv]; //记录最短路径
    int n,m;
    
    bool Bellman(int s){ 
    	fill(d,d+maxv,INF);
    	d[s] = 0;
    	for(int i=0; i<n-1; i++){  //执行n-1轮操作，n为顶点数 
    		for(int u=1; u<=n; u++){  //每轮操作遍历所有边,顶点从1开始编号 
    			for(int j=0; j<Adj[u].size(); j++){ 
    				int v = Adj[u][j].v;
    				int dis = Adj[u][j].dis;
    				if(d[v] > d[u]+dis){ 
    					d[v] = d[u] + dis;//松弛操作 
    				}
    			}
    		}
    	}
    	// 判断负环代码
    	for(int u=1; u<=n; u++){ //遍历每一条边 
    		for(int j=0; j<Adj[u].size();j++){ 
    			int v = Adj[u][j].v;
    			int dis = Adj[u][j].dis;
    			if(d[u]+dis < d[v]){  //任然可以被松弛 
    				return false;//表名图中有从源点可达的负环 
    			} 
    		} 
    	}
    	return true;
    }