算法概论实验四

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
实验四

实验目的与要求：掌握动态规划方法的基本思想与设计策略。
1．多段图中的最短路径问题
【问题描述】
建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。
2．有向无环图中的最短路径问题
【问题描述】
建立一个从源点S到终点E的有向无环图，设计一个动态规划算法求出从S到E的最短路径值，并输出相应的最短路径。

#1．多段图中的最短路径问题

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
#include<iostream>
#include<cmath>
#include<string.h>
using namespace std;
int  dp[1222222],alone[1222222],a[1222222];
int main()
{
    int i,j,n,m;
    while(~scanf("%d",&m))
    {
        scanf("%d",&n);
		memset(dp,0,sizeof(dp));
		memset(alone ,0,sizeof(alone));
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        int tmax;         
        for(i=1;i<=m;i++)//★分i段
        {
            tmax=-(1<<30);
		
            for(j=i;j<=n;j++)
            {
                dp[j]=_cpp_max(dp[j-1],alone[j-1])+a[j];


  printf("%2d %2d %2d\n",a[j],alone[j-1],dp[j]);
                if(j>i)alone[j-1]=tmax;

                if(tmax<dp[j])tmax=dp[j];
	
            }

        }
        printf("%d\n",tmax);
    }
    return 0;
}

#2．有向无环图中的最短路径问题

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
#include <iostream>
#include <limits.h>
using namespace std;

void Init_Graph(int N,int **S)
{
	int i,j;
	cout<<"输入边的长度：输入1 2 4 表示点1 与 2的边的长度为 4：首数字为0表示结束输入"<<endl;
	cin>>i;
	while(i!=0)
	{
		cin>>j;
		cin>>S[i][j];
		cin>>i;
	}
}

void DP(int N,int **S,int *dist,int *from)
{
	int i,j;
	for(j=0;j<N+1;j++)
	{
		if(S[1][j]<INT_MAX)
		{
			dist[j]=S[1][j];
			from[j]=1;
		}
	}

	for(j=2;j<N+1;j++)
	{
		for(i=2;i<j;i++)
		{
			if(S[i][j]<INT_MAX)
			{
				if(dist[i]+S[i][j]<dist[j])
				{
					dist[j]=dist[i]+S[i][j];
					from[j]=i;
				}
			}
		}
	}
	cout<<"最短路径为：";
	i=6;
	cout<<N<<"  "<<from[i]<<"  ";
	i=from[i];
	while(i!=1)
	{
		cout<<from[i]<<"  ";
		i=from[i];
	}
	cout<<"\n";
	cout<<"最短距离为："<<dist[N]<<endl;
}

int main()
{
	int N;
	int **S,*dist,*from;
	int i,j;
	cout<<"输入点的个数：";  
    cin>>N;

	S=new int*[N+1];
	for(i=0;i<N+1;i++)
	{
		S[i]=new int[N+1];
		for(j=0;j<N+1;j++)
		{
			S[i][j]=INT_MAX;
		}
	}
	dist=new int[N+1];
	for(i=0;i<N+1;i++)
	{
		dist[i]=INT_MAX;
	}
    from=new int[N+1];
	for(i=0;i<N+1;i++)
	{
		from[i]=0;
	}

	Init_Graph(N,S);
	DP(N,S,dist,from);

	for(i=0;i<N+1;i++)
	{
		delete []S[i];
	}
	delete []S;
	delete []dist;
	delete []from;
	return 0;
}