本文主要是介绍7-3 最短路径 (20 分)（分支限界+思路+详解），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一：题目

给定一个有N个顶点和E条边的无向图，顶点从0到N−1编号。请判断给定的两个顶点之间是否有路径存在。如果存在，给出最短路径长度。 这里定义顶点到自身的最短路径长度为0。 进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。 随后E行，每行给出一条边的两个顶点。每行中的数字之间用1空格分隔。 最后一行给出两个顶点编号i，j（0≤i,j<N）,i和j之间用空格分隔。

输出格式:
如果i和j之间存在路径，则输出"The length of the shortest path between i and j is X."，X为最短路径长度， 否则输出"There is no path between i and j."。

输入样例1:

7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 3

结尾无空行
输出样例1:

The length of the shortest path between 0 and 3 is 2.

结尾无空行
输入样例2:

7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6

结尾无空行
输出样例2:

There is no path between 0 and 6.

二：思路

分析:1.这个题没给边的权值，但我们通过示例可以大概知道默认的为 每条边的权值为1

思路:1.先判断输入的值之间是否有路径,可以通过DFS来遍历其中一个顶点的所有邻接点
如果另一个邻接点没有在其中，那么就说明 其是不通的
2.如果两个点是相连通的，那么我们接下来就是BFS遍历
3.我们将图的信息转换成树的结构，我们在遍历树的时候采用的就是BFS
1>:首先我们将给定的两个结点的其中一个结点入队，接下来，将其出队当作扩展结点
这个新节点（在树当中的）有自己路径，还有权值和，以及层数。
2>:然后就判断这个结点（树）是否已经到达了目标结点，如果到，那么判断这个结点
的路径和跟bestw的值看是否更新，
如果没到目标结点，判断其路径和跟已知bestw 如果比起大就进行剪枝操作
再接下来，就是开始遍历其邻接点入队操作。

4.注意代码中的 node.x[t] 这其中 t代表的是层数，node.x[t]代表的是图的一个结点号

三：上码

/**
	分析:1.这个题没给边的权值，但我们通过示例可以大概知道默认的为 每条边的权值为1 

    思路:1.先判断输入的值之间是否有路径,可以通过DFS来遍历其中一个顶点的所有邻接点
		   如果另一个邻接点没有在其中，那么就说明 其是不通的 
		 2.如果两个点是相连通的，那么我们接下来就是BFS遍历 
		 3.我们将图的信息转换成树的结构，我们在遍历树的时候采用的就是BFS
		    1>:首先我们将给定的两个结点的其中一个结点入队，接下来，将其出队当作扩展结点 
			  这个新节点（在树当中的）有自己路径，还有权值和，以及层数。
	      	2>:然后就判断这个结点（树）是否已经到达了目标结点，如果到，那么判断这个结点
			  的路径和跟bestw的值看是否更新，
			  如果没到目标结点，判断其路径和跟已知bestw 如果比起大就进行剪枝操作
			  再接下来，就是开始遍历其邻接点入队操作。	 
	 
	   4.注意代码中的 node.x[t] 这其中 t代表的是层数，node.x[t]代表的是图的一个结点号 
*/

#include<bits/stdc++.h>
using namespace std;

int INF = 999999;
int maps[11][11];//存图用的数组。 
int N,M;
int bestw = INF;
int cnt = 0;
int vis2[11] = {0};

struct Node{
	int x[100];//记录树的路径
	int layer;//记录层数
	int cl;//记录已经走过的路径长度 
}; 

bool operator<(const Node& a,const Node& b){
	return a.cl > b.cl;//升序处理 小的数在前面 
} 

//判断是否可达
void dfs(int a,int b){
	
	if(a == b){
		cnt = 1;
		return;
	}	
	vis2[a] = 1;
	for(int i = 0; i < N; i++){
		if(vis2[i] != 1 && maps[a][i] == 1){	
			dfs(i,b); 
		}
	} 
	
//	cout << "wyj";
} 
// 
//求取最短路径 
void bfs(int a,int b){
	
	priority_queue<Node>q; 
	
	Node node1;
	node1.cl = 0;
	node1.layer = 0;//我们是从第0层开始的 
	
	for(int i = 0; i < N; i++){//初始化路径 
		node1.x[i] = i; 
	}   
	
	node1.x[0] = a;
	
	q.push(node1);
	
	while(!q.empty()){	
	
		int vis[11] = {0};
		vis[a] = 1;
	
		Node newnode;//扩展结点 
		newnode = q.top();
		q.pop();
		
		int t1 = newnode.layer;//代表当前的层数 
		int t2 = newnode.x[t1];//代表当前所到达的结点号 
			
	    //比较该节点的路径中，是否到达了目标结点
		if(t2 == b) {
			if(newnode.cl < bestw){
				bestw = newnode.cl;
			}else{//到达目标结点 如果还未成功的话，那就不用继续往下遍历了 
				continue;
			}	
		}
		
		if(newnode.cl >= bestw)//进行剪枝操作 
			continue;
		
		//将其扩展结点的邻接点入队
		for(int j = 0; j < N; j++){
			
			if(vis[j] != 1 && newnode.cl + maps[t2][j] < bestw) {
				
				int flag = 1; 
				for(int k = 0; k < t1; k++){
					if(newnode.x[k] == j){
						flag = 0;		
					}	
				} 
				
				if(flag == 0) continue; //这里主要处理的就是  不让这个路径往回走 
				
				vis[j] = 1; 
				
				//我们创建一个新的结点（在排列树当中） 
				Node node2;
				node2.cl = newnode.cl + maps[t2][j];
				node2.layer = t1 + 1;
				
				for(int i = 0; i < N; i++){
					node2.x[i] = newnode.x[i];
				}		
				swap(node2.x[t1+1],j);//t1代表的是层数，node.x[t1]代表该层数所对应图当中的结点号 
				
				q.push(node2);			
			}			
		}		 
			
	} 	
} 

int main(){	 

	int target1,target2;//两个目标结点 
	cin >> N >> M;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(i == j){
				maps[i][j] = 0;
			}
			maps[i][j] = INF;
		}
	}
	 
	for(int i = 0; i < M; i++){
		int side1,side2;
		cin >> side1 >> side2;
		maps[side1][side2] = 1;
		maps[side2][side1] = 1;  
	}
	
	cin >> target1 >> target2; 
	
	dfs(target1,target2);
	
	if(cnt == 0){
	   cout << "There is no path between "<< target1 <<" and " << target2 << ".";
	} else{
	   bfs(target1,target2);
	   cout << "The length of the shortest path between "<<target1 << " and "<< target2<<" is "<< bestw<<".";	
	}
		
	
} 




//7 6
//0 1
//2 3
//1 4
//0 2
//1 3
//5 6
//0 6


//7 7
//0 1
//2 3
//1 4
//0 2
//1 3
//5 6
//4 5
//0 6


//7 7
//0 1
//2 3
//1 4
//0 2
//1 3
//5 6
//4 5
//6 2


//7 7
//0 1
//2 3
//1 4
//0 2
//1 3
//5 6
//4 5
//4 2

四：总结

分支限界如果只是会BFS,是远远不够的，即便我提前已经做过BFS的练习题了，其还是有一定 相当的难度，注意自己一定要画出响应的图解，开始帮助理解算法和写代码

随手拍照，跟着考研上凌晨自习，感触颇多，没有了所谓大家的卷，其实都是在为自己人生路去努力拼搏，太喜欢这种学习的氛围了，感觉像是回到了高中，那种简单纯碎的学习和快乐 加油 大家

这篇关于7-3 最短路径 (20 分)（分支限界+思路+详解）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！