实验五动态规划实验
一、实验目的
1.掌握动态规划算法的基本思想。

二、实验内容
1、参考教材描述，使用动态规划算法求解多段图的最短路径问题。

#include <iostream.h>
#include <stdlib.h>
#define max_value 10000
#define zero_value 0
typedef struct NODE{
int v_num;
int len;
struct NODE *next;
}LinkStackNode,LinkStack;
/* typedef struct PNODE{
int data;
int len;
struct PNODE *next;
}*LinkStackPnode,*LinkStack;*/
int fgraph(LinkStack top[],int route[],int n)
{ int i;
LinkStackNode *pnode;
int *path=new int[n];
int *cost=new int[n];
int min_cost;
for(i=0;i<n;i++)
{
cost[i]=max_value;
path[i]=-1;
route[i]=0;
}
cost[n-1]=zero_value;
for(i=n-2;i>=0;i--)
{
pnode=top[i].next;
while(pnode!=NULL)
{
if(pnode->len+cost[pnode->v_num]<cost[i])
{
cost[i]=pnode->len+cost[pnode->v_num];
path[i]=pnode->v_num;
}
pnode = pnode-> next;
}
}
i=0;
while((route[i]!=n-1)&&(path[i]!=-1))
{
i++;
route[i]=path[route[i-1]];
}
min_cost=cost[0];
delete path;
delete cost;
return min_cost;
}
int push(LinkStack top[],int i,int x,int y) {
LinkStackNode *temp;
temp=new LinkStackNode;
if(temp==NULL)
return 0;
temp->v_num=x;
temp->len=y;
temp->next=top[i].next;
top[i].next=temp;
return 1;
}
void main()
{
LinkStack top[10];
int cost;
//int route[M];
int route[10];
int a;
//int b;
for (int i = 0; i<10; i++) {
top[i].v_num= i;
top[i].len = 0;
top[i].next = NULL;
}
push(top,0,1,4);
push(top,0,2,1);
push(top,0,3,3);
push(top,1,4,9);
push(top,1,5,6);
push(top,2,3,1);
push(top,2,4,6);
push(top,2,5,7);
push(top,2,6,8);
push(top,3,5,4);
push(top,3,6,7);
push(top,4,7,5);
push(top,4,8,6);
push(top,5,7,8);
push(top,5,8,6);
push(top,6,7,6);
push(top,6,8,5);
push(top,7,9,7);
push(top,8,9,3);
cost=fgraph( top,route,10);
cout<<"min_cost="<<cost<<endl;
//a=route[1];
//cout<<a<<endl;
for(i=0;i<6;i++)
cout<<"最短路径为："<<route[i]<<endl; }。