Java教程

图的最短路径问题(一)--深度优先搜索算法解决单源单向图

本文主要是介绍图的最短路径问题(一)--深度优先搜索算法解决单源单向图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本人在博客园的第一篇题解,日期2022年3月8日晚上7点。

前言:本文适合有一定dfs基础和图论基础的人借鉴。

1.深度优先搜索算法(Deep First Search):

  不过度赘述,利用递归调用。下面给出模板。

1 void dfs(参数列表){
2     //剪枝
3 
4     //递归结束
5 
6     //递归
7     
8 }   

2.题目:(P3371 【模板】单源最短路径(弱化版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

 

 

 

 

本题中,dfs核心代码如下:

 1 void dfs(int cur,int des,int sum){    
 2     //剪枝 
 3     if(sum>=minSum[des])return;
 4     //找到目标点,结束递归
 5     if(cur==des){
 6         minSum[des]=sum;//更新新小值
 7         return;
 8     }
 9     //递归
10     for(int i=1;i<=n;i++){
11         if( edge[cur][i]==-1)continue;
12         dfs(i,des,sum+edge[cur][i]);
13     }
14 }

 

其中,cur表示当前到达的元素,des表示终点元素,sum表示当前已经累计的合。

minSum[des]表示从s到当前终点的最短路径权值合。

剪枝部分:已经累积的合已然超过了之前搜索到的最小值,直接结束递归。

当cur==des,也就是找到终点元素,当前路径打通,结束递归,并且一定此时有sum<minSum[des]。

这里的edge[A][B]的值,表示从A->B路径的权值。

3.下面给出完整代码:

 1 /***
 2 
 3 ***/
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 //点,边,出发点
 8 // m 行 u v w
 9 // u->v权值w
10 const int Max=20;
11 const int Inf=2147483647;
12 int n,m,s;
13 int edge[Max][Max];
14 int minSum[Max];
15 void dfs(int cur,int des,int sum){    
16     //剪枝 
17     if(sum>=minSum[des])return;
18     //找到目标点,结束递归
19     if(cur==des){
20         minSum[des]=sum;//更新新小值
21         return;
22     }
23     //递归
24     for(int i=1;i<=n;i++){
25         if( edge[cur][i]==-1)continue;
26         dfs(i,des,sum+edge[cur][i]);
27     }
28 }
29 int main() {
30     cin>>n>>m>>s;
31     for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)edge[i][j]=-1;    //初始化邻接矩阵
32     while(m--){
33         int u,v,w;
34         cin>>u>>v>>w;
35         edge[u][v]=w;
36     }
37     fill(minSum+1,minSum+n+1,Inf);
38     for(int i=1;i<=n;i++){
39         dfs(s,i,0);
40         cout<<minSum[i]<<" ";
41     }
42     return 0;
43 }
44 
45     
46     

 

 

其中,edge邻接矩阵需要初始化,-1表示不连通。

fill()语句语法:fill(填充起始地址,结束地址,填充值); 

用来把数组整体赋值为一个非0值。

值得注意的是,当数据过大时,会出现stack overflow错误!栈溢出。

解决办法:换其他算法,待更新。

 

这篇关于图的最短路径问题(一)--深度优先搜索算法解决单源单向图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!