DAG求单源最短距离

1.题目描述：

上图所示的图为有向无环图(DAG)，现在需要求解从结点$s$出发到达结点$t$的最短距离。

2.基本思路

由于该图为有向无环图因此其满足最优子结构的性质。定义函数$f(i)$，该函数表示从原点出发到达结点$i$的最短距离。因此我们可以得到以下的递推关系式:
f ( T ) = m i n { f ( C ) + 20 , f ( D ) + 10 } f ( D ) = m i n { f ( B ) + 20 , f ( A ) + 10 , f ( C ) + 5 } . . . f(T)=min { f(C)+20,f(D)+10 } \ f(D)=min {f(B)+20,f(A)+10,f(C)+5 } \ ... f(T)=min{f(C)+20,f(D)+10}f(D)=min{f(B)+20,f(A)+10,f(C)+5}...

3.代码实现

该问题的求解思路为采用拓扑排序的方法，每次处理入度为0的结点$i$，更新结点$i$所能到达的结点的当前最短距离，然后更新过后的结点入度均减1，直到最后完成整个拓扑排序的过程，输出到达终点的距离。

在实现代码的时候需要维护好以下的信息：
与结点$i$相邻的结点信息，结点之间的权重，从起始结点出发到达当前结点的最短距离。

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#define N 101
using namespace std;
map<char,vector<char>> Near;//维护与每个结点相连的结点的信息
map<char,map<char,int>> TD;//记录两两结点之间的距离
map<char,int> Dis;//记录从起点到当前结点的距离
map<char,int> degree;//记录每个结点的入度
queue<char> Q;//存储入度为0的结点
int main()
{
char c1,c2;
int w=-1;
while(cin>>c1>>c2>>w){
if(w==0)break;//以边权为0做为输入的结束条件
Near[c1].push_back(c2);
TD[c1][c2]=w;
degree[c2]+=1;
}
for(auto it=degree.begin();it!=degree.end();it++){
if(it->second==0){
Q.push(it->first);
}
Dis[it->first]=123123123;
}
Dis['s']=0;
Q.push('s');//其实结点入队
while(!Q.empty()){
char tmp = Q.front();
Q.pop();
for(int i=0;i<Near[tmp].size();i++){
Dis[Near[tmp][i]]=min(Dis[Near[tmp][i]],Dis[tmp]+TD[tmp][Near[tmp][i]]);
degree[Near[tmp][i]]--;
if(degree[Near[tmp][i]]==0)
Q.push(Near[tmp][i]);
}
}
cout<<"The minimum distance from s to t is:"<<Dis['t']<<endl;
return 0;
}
/*
INPUT：
s a 10
s b 20
a c 30
a d 10
b d 20
c d 5
c t 20
d t 10
0 0 0
OUTPUT:
The minimum distance from s to t is:30
*/

最后

以上就是体贴豆芽为你收集整理的DAG-dp DAG求单源最短距离 的全部内容，希望文章能够帮你解决DAG-dp DAG求单源最短距离 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。