有向无环图的最长简单路径

给定一个有向无环图$G=(V,E)$,边权重为实数,给定图中的两个顶点$k,t$,设计动态规划算法,求从k到t的最长简单路径,子问题图是怎样的?算法的效率如何?

算法分析:
该问题不能够用贪心求解,假设从k出发,每一步取得weight最大的边,按这样的路径,并不能够保证能走到终点t。所以考虑动态规划算法。
该问题满足动态规划算法的两个特征:
一、最优子结构:
从k出发到t的最优路径,一定是$max(best \, path \, A_1 \, to \,\, t+weight[A_0][A_1])$,其中$A0—>A1—>\cdots t$和$B0—>B1—>\cdots t$等等的诸多方案中的最优方案,构成了最优解。符合“剪贴”性质。

二、重叠子结构

有上面的公式可知,子问题:$A0—>A1—>\cdots t$会被反复求解。

01

状态转移函数:

1
2
3
4
5
6
7
int q=weight[k][t];
for(int i=k+1;i<=t && weight[k][i];i++)
{
q=max(q,weight[k][i]+Find_longest_path(weight,numVertexes,i,t,r));
}
r[k]=q;
return q;

算法实现

Graphic_longest_path.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <iostream>
#include <iomanip>
using namespace std;
#define INITWEIGHT 0
//用矩阵实现图
class graph
{
private:
bool isWeighted; //是否带权?
bool isDirected; //是否有向?
int numV; //顶点数
int numE; //边数
int **matrix; //邻接矩阵
public:
graph(int numV,bool isWeighted=false,bool isDirected=false);
void createGraph();
~graph();
int getVerNums()
{
return numV;
}
int getEdgeNums()
{
return numE;
}
int **getWeight()
{
return matrix;
}
void setEdgeWeight(int beg,int end,int weight);
void printAdjacentMatrix();
//检查输入
bool check(int i,int j,int w=1);
};
//类的实现
graph::graph(int numV,bool isWeighted,bool isDirected)
{
while(numV<=0)
{
cout<<"Vertex is wrong! Please enter again! "<<endl;
cin>>numV;
}
this->numV=numV;
this->isWeighted=isWeighted;
this->isDirected=isDirected;
//private之后的成员可以被类的成员函数访问,但是不能够被使用该类的代码访问
matrix=new int *[numV];
for(int i=0;i<numV;i++)
matrix[i]=new int [numV];
//对图进行初始化
if(!isWeighted) //无权图
{
//对所有的权值初始化为0
for(int i=0;i<numV;i++)
for(int j=0;j<numV;j++)
matrix[i][j]=0;
}
else //有权图
{
for(int i=0;i<numV;i++)
for(int j=0;j<numV;j++)
matrix[i][j]=INITWEIGHT;
}
}
//建图
void graph::createGraph()
{
cout<<"input edges: "<<endl;
while(cin>>numE && numE<0)
cout<<"wrong input! "<<endl;
int i,j,w;
if(!isWeighted) //无权图
{
if(!isDirected) //无向图
{
cout<<"Input begin and end "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j;
while(!check(i,j))
{
cout<<"wrong edges, input again: "<<endl;
cin>>i>>j;
}
matrix[i][j]=matrix[j][i]=1;
}
}
else
{
cout<<"enter begin and end "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j;
while(!check(i,j))
{
cout<<"wrong edges, input again: "<<endl;
cin>>i>>j;
}
matrix[i][j]=1;
}
}
}
else //有权图
{
if(!isDirected) //无向图
{
cout<<"enter begin, end, and weight: "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j>>w;
while(!check(i,j,w))
{
cout<<"wrong edges,input again: "<<endl;
cin>>i>>j>>w;
}
matrix[i][j]=matrix[j][i]=w;
}
}
else
{
cout<<"begin, end, and weight: "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j>>w;
while(!check(i,j,w))
{
cout<<"wrong edges, input again: "<<endl;
cin>>i>>j>>w;
}
matrix[i][j]=w;
}
}
}
}
graph::~graph() //析构函数
{
for(int i=0;i<numV;i++)
delete[] matrix[i];
delete[] matrix;
}
//设置指定边权值:
void graph::setEdgeWeight(int beg,int end,int weight)
{
if(isWeighted)
{
while(!check(beg,end,weight))
{
cout<<"wrong input, input again:"<<endl;
cin>>beg>>end>>weight;
}
if(isDirected)
matrix[beg][end]=weight;
else
matrix[beg][end]=matrix[end][beg]=weight;
}
else
{
while(!check(beg,end,1))
{
cout<<"wrong input, input again: "<<endl;
cin>>beg>>end;
}
if(isDirected) //对邻接矩阵的值进行反转,重置,1变成0,0变成1
matrix[beg][end]=1-matrix[beg][end];
else
matrix[beg][end]=matrix[end][beg]=1-matrix[beg][end];
}
}
//输入检查
bool graph::check(int i,int j,int w)
{
if(i>=0 && i<numV && j>=0 && j<numV && w>0)
return true;
else
return false;
}
void graph::printAdjacentMatrix()
{
cout.setf(ios::left);
cout<<setw(4)<<" ";
for(int i=0;i<numV;i++)
cout<<setw(4)<<i;
cout<<endl;
for(int i=0;i<numV;i++)
{
cout<<setw(4)<<i;
for(int j=0;j<numV;j++)
cout<<setw(4)<<matrix[i][j];
cout<<endl;
}
}

dynamic_longest_path.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "Graphic_longest_path.h"
#include <iostream>
#include <vector>
#define INFINITY 0x7fffffff
int max(int a,int b)
{
return a>b?a:b;
}
int Find_longest_path(int **weight,int numVertexes,int k,int t,vector<int> &r) //寻找k到t的最短路径
{
if(r[k]>=0)
return r[k];
if(k==t)
{
int q=0;
r[k]=q;
return q;
}
else
{
int q=weight[k][t];
for(int i=k+1;i<=t && weight[k][i];i++)
{
q=max(q,weight[k][i]+Find_longest_path(weight,numVertexes,i,t,r));
}
r[k]=q;
return q;
}
}
int dynamic_longest_path(int **weight,int numVertexes,int k,int t)
{
vector<int> r;
r.resize(numVertexes);
for(int i=0;i<numVertexes;i++)
r[i]=-INFINITY;
return Find_longest_path(weight,numVertexes,k,t,r);
}

Graphic_longest_path.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "dynamic_longest_path.h"
#include <iostream>
int main()
{
cout<<"AdjacentMatrix Graphic: "<<endl;
bool isDirected, isWeighted;
int numV;
cout<<"Create Graphics: "<<endl;
cout<<"input Vertexes: ";
cin>>numV;
cout<<"Is weighted? 0(no), 1(yes) : ";
cin>>isWeighted;
cout<<"IS directed? 0(no), 1(yes) : ";
cin>>isDirected;
graph graph(numV,isWeighted,isDirected);
cout<<"This is a ";
isDirected ? cout<<"Directed " : cout<<"Undirected: ";
isWeighted ? cout<<"Weighted " <<endl : cout<<"Unweighted "<<endl;
graph.createGraph();
cout<<"print AdjacentMatrix: "<<endl;
graph.printAdjacentMatrix();
cout<<endl;
int k,t;
cout<<"input k, t :"<<endl;
cin>>k>>t;
int numVertex=graph.getVerNums();
int **weight_dynamic=graph.getWeight();
cout<<"test: ";
cout<<weight_dynamic[k][t]<<endl;
int result=dynamic_longest_path(weight_dynamic,numVertex,k,t);
cout<<"The result is :"<<endl;
cout<<result<<endl;
int beg, end, weight;
bool flag;
cout<<"Adjust the weight, no(0), yes(1): "<<endl;
cin>>flag;
if(flag)
{
if(isWeighted)
{
cout<<"Enter edges--begin, end, and weight: "<<endl;
cin>>beg>>end>>weight;
graph.setEdgeWeight(beg,end,weight);
}
else
{
cout<<"Enter edges--begin, end: "<<endl;
cin>>beg>>end;
graph.setEdgeWeight(beg,end,1);
}
cout<<"Successed!"<<endl;
cout<<"Print AdjacentMatrix: "<<endl;
graph.printAdjacentMatrix();
}
return 0;
}

重构解

为了能够输出最短路径的方案,可以对解进行重构:

Graphic_longest_path.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <iostream>
#include <iomanip>
using namespace std;
#define INITWEIGHT 0
//用矩阵实现图
class graph
{
private:
bool isWeighted; //是否带权?
bool isDirected; //是否有向?
int numV; //顶点数
int numE; //边数
int **matrix; //邻接矩阵
public:
graph(int numV,bool isWeighted=false,bool isDirected=false);
void createGraph();
~graph();
int getVerNums()
{
return numV;
}
int getEdgeNums()
{
return numE;
}
int **getWeight()
{
return matrix;
}
void setEdgeWeight(int beg,int end,int weight);
void printAdjacentMatrix();
//检查输入
bool check(int i,int j,int w=1);
};
//类的实现
graph::graph(int numV,bool isWeighted,bool isDirected)
{
while(numV<=0)
{
cout<<"Vertex is wrong! Please enter again! "<<endl;
cin>>numV;
}
this->numV=numV;
this->isWeighted=isWeighted;
this->isDirected=isDirected;
//private之后的成员可以被类的成员函数访问,但是不能够被使用该类的代码访问
matrix=new int *[numV];
for(int i=0;i<numV;i++)
matrix[i]=new int [numV];
//对图进行初始化
if(!isWeighted) //无权图
{
//对所有的权值初始化为0
for(int i=0;i<numV;i++)
for(int j=0;j<numV;j++)
matrix[i][j]=0;
}
else //有权图
{
for(int i=0;i<numV;i++)
for(int j=0;j<numV;j++)
matrix[i][j]=INITWEIGHT;
}
}
//建图
void graph::createGraph()
{
cout<<"input edges: "<<endl;
while(cin>>numE && numE<0)
cout<<"wrong input! "<<endl;
int i,j,w;
if(!isWeighted) //无权图
{
if(!isDirected) //无向图
{
cout<<"Input begin and end "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j;
while(!check(i,j))
{
cout<<"wrong edges, input again: "<<endl;
cin>>i>>j;
}
matrix[i][j]=matrix[j][i]=1;
}
}
else
{
cout<<"enter begin and end "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j;
while(!check(i,j))
{
cout<<"wrong edges, input again: "<<endl;
cin>>i>>j;
}
matrix[i][j]=1;
}
}
}
else //有权图
{
if(!isDirected) //无向图
{
cout<<"enter begin, end, and weight: "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j>>w;
while(!check(i,j,w))
{
cout<<"wrong edges,input again: "<<endl;
cin>>i>>j>>w;
}
matrix[i][j]=matrix[j][i]=w;
}
}
else
{
cout<<"begin, end, and weight: "<<endl;
for(int k=0;k<numE;k++)
{
cin>>i>>j>>w;
while(!check(i,j,w))
{
cout<<"wrong edges, input again: "<<endl;
cin>>i>>j>>w;
}
matrix[i][j]=w;
}
}
}
}
graph::~graph() //析构函数
{
for(int i=0;i<numV;i++)
delete[] matrix[i];
delete[] matrix;
}
//设置指定边权值:
void graph::setEdgeWeight(int beg,int end,int weight)
{
if(isWeighted)
{
while(!check(beg,end,weight))
{
cout<<"wrong input, input again:"<<endl;
cin>>beg>>end>>weight;
}
if(isDirected)
matrix[beg][end]=weight;
else
matrix[beg][end]=matrix[end][beg]=weight;
}
else
{
while(!check(beg,end,1))
{
cout<<"wrong input, input again: "<<endl;
cin>>beg>>end;
}
if(isDirected) //对邻接矩阵的值进行反转,重置,1变成0,0变成1
matrix[beg][end]=1-matrix[beg][end];
else
matrix[beg][end]=matrix[end][beg]=1-matrix[beg][end];
}
}
//输入检查
bool graph::check(int i,int j,int w)
{
if(i>=0 && i<numV && j>=0 && j<numV && w>0)
return true;
else
return false;
}
void graph::printAdjacentMatrix()
{
cout.setf(ios::left);
cout<<setw(4)<<" ";
for(int i=0;i<numV;i++)
cout<<setw(4)<<i;
cout<<endl;
for(int i=0;i<numV;i++)
{
cout<<setw(4)<<i;
for(int j=0;j<numV;j++)
cout<<setw(4)<<matrix[i][j];
cout<<endl;
}
}

longest_path_constitute.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "Graphic_longest_path.h"
#include <iostream>
#include <vector>
#define INFINITY 0x7fffffff
int max(int a,int b)
{
return a>b?a:b;
}
int Find_longest_path(int **weight,int numVertexes,int k,int t,vector<int> &r,int *solution) //寻找k到t的最短路径
{
if(r[k]>=0)
return r[k];
if(k==t)
{
int q=0;
r[k]=q;
solution[k]=t;
return q;
}
else
{
int q=weight[k][t];
if(weight[k][t])
solution[k]=t;
for(int i=k+1;i<=t && weight[k][i];i++)
{
int tmp=max(q,weight[k][i]+Find_longest_path(weight,numVertexes,i,t,r,solution));
if(tmp>q)
{
q=tmp;
solution[k]=i;
}
}
r[k]=q;
return q;
}
}
int dynamic_longest_path(int **weight,int numVertexes,int k,int t,int *solution)
{
vector<int> r;
r.resize(numVertexes);
for(int i=0;i<numVertexes;i++)
{
r[i]=-INFINITY;
}
//完成初始化
return Find_longest_path(weight,numVertexes,k,t,r,solution);
}
void print_solution(int *solution,int k,int t)
{
if(solution[k]==-1)
cout<<"The path is not exist! "<<endl;
else
{
cout<<"The result is : "<<endl;
cout<<" "<<k<<" --> ";
while(k!=t)
{
cout<<solution[k];
if(solution[k]!=t)
{
cout<<" --> ";
}
k=solution[k];
}
cout<<endl;
}
}

Graphic_longest_path.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "longest_path_constitute.h"
#include <iostream>
int main()
{
cout<<"AdjacentMatrix Graphic: "<<endl;
bool isDirected, isWeighted;
int numV;
cout<<"Create Graphics: "<<endl;
cout<<"input Vertexes: ";
cin>>numV;
cout<<"Is weighted? 0(no), 1(yes) : ";
cin>>isWeighted;
cout<<"IS directed? 0(no), 1(yes) : ";
cin>>isDirected;
graph graph(numV,isWeighted,isDirected);
cout<<"This is a ";
isDirected ? cout<<"Directed " : cout<<"Undirected: ";
isWeighted ? cout<<"Weighted " <<endl : cout<<"Unweighted "<<endl;
graph.createGraph();
cout<<"print AdjacentMatrix: "<<endl;
graph.printAdjacentMatrix();
cout<<endl;
int k,t;
cout<<"input k, t :"<<endl;
cin>>k>>t;
int numVertex=graph.getVerNums();
int **weight_dynamic=graph.getWeight();
cout<<"test: ";
cout<<weight_dynamic[k][t]<<endl;
//初始化solution:
int *solution=new int[numVertex+1];
for(int i=0;i<numVertex;i++)
solution[i]=-1;
//返回最优解:
int result=dynamic_longest_path(weight_dynamic,numVertex,k,t,solution);
cout<<"The result is :"<<endl;
cout<<result<<endl;
//返回solution的解,注意delete[]
cout<<"The solution is "<<endl;
print_solution(solution,k,t);
int beg, end, weight;
bool flag;
cout<<"Adjust the weight, no(0), yes(1): "<<endl;
cin>>flag;
if(flag)
{
if(isWeighted)
{
cout<<"Enter edges--begin, end, and weight: "<<endl;
cin>>beg>>end>>weight;
graph.setEdgeWeight(beg,end,weight);
}
else
{
cout<<"Enter edges--begin, end: "<<endl;
cin>>beg>>end;
graph.setEdgeWeight(beg,end,1);
}
cout<<"Successed!"<<endl;
cout<<"Print AdjacentMatrix: "<<endl;
graph.printAdjacentMatrix();
}
return 0;
}

输出结果

02

原创技术分享,您的支持鼓励我继续创作