动态规划之最短路径问题源代码
#include "stdio.h"
#include "conio.h"
#define n 16 /*图的顶点数*/
#define k 7 /*图的段数*/
#define l 30
#define MAX 100
typedef int NodeNumber;/*节点编号*/
typedef int CostType;/*成本值类型*/
CostType cost[n][n];
NodeNumber path[k];
NodeNumber cur=-1;
void creategraph(CostType *cost[n][n]) /*创建图的成本矩阵*/ {
int i,j,x,y,value;
for(i=0;i<n;i++)
for(j=0;j<n;j++) cost[i][j]=0;
printf("\nEnter the cost of graph:\n");
for(i=0;i<l;i++)
{
scanf("%d,%d,%d",&x,&y,&value);
cost[x][y]=value;
}
}
void outgraph(CostType *cost[n][n]) /*输出图的成本矩阵*/ {
int i,j;
printf("Print the cost of graph:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) printf("%2d",cost[i][j]);
printf("\n");
}
}
/*使用向前递推算法求多段图的最短路径*/
void FPath(CostType *cost[n][n],NodeNumber *path[k]) {
int i,j,leng,temp,v[n],d[n];
for(i=0;i<n;i++) v[i]=0;
for(i=n-2;i>=0;i--)
{ leng=MAX;
for(j=i+1;j<=n-1;j++)
if(cost[i][j]>0 && (cost[i][j]+v[j])<leng)
{
leng=cost[i][j]+v[j];temp=j;
}
v[i]=leng;
d[i]=temp;
}
path[0]=0;
path[k-1]=n-1;
for(i=1;i<=k-2;i++) path[i]=d[path[i-1]]; }
/*输出最短路径序列*/
void outpath(NodeNumber *path[k])
{
int i;
printf("\nPrint the shortest treet:\n");
for(i=0;i<k;i++) printf("%3d",path[i]); }
main()
{
NodeNumber m,t;
creategraph(&cost);
outgraph(&cost);
FPath(&cost,&path);
outpath(&path);
}。