算法概论实验四

算法概论实验

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

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

#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．有向无环图中的最短路径问题

#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;
}