本文主要是介绍C语言及程序设计进阶例程-28 动态规划法问题求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
贺老师教学链接 C语言及程序设计进阶 本课讲解
最短路径问题
#include<stdio.h>
#define n 7
#define x 9999 /*用一个尽可能大的开销,代表结点之间没有通路*/
int map[n][n]= /*对图7.33中交通网的描述,map[i][j]代表i结点到j结点的开销*/
{{x,4,5,8,x,x,x},{x,x,x,6,6,x,x},{x,x,x,5,x,7,x},{x,x,x,x,8,9,9},{x,x,x,x,x,x,5},{x,x,x,x,x,x,4},{x,x,x,x,x,x,x}
};int main()
{int cost[n]; /*记录出发点到每个结点的最短路径*/int path[n]= {0}; /*记录到达各个结点的最短路径中,上一个结点的编号*/int i,j;int minCost, minNode;cost[0]=0; /*出发点到自己的开销为0*/for(i=1; i<n; i++) /*循环过程中,求出到每个结点的最小开销,并且记录使开销最小的前一结点*/{minCost=x;for(j=0; j<i; j++){if(map[j][i]!=x)if((cost[j]+map[j][i])<minCost){minCost=cost[j]+map[j][i];minNode=j;}}cost[i]=minCost;path[i]=minNode;}printf("最短路径的开销为: %d\n",cost[n-1]); /*输出最短路径的开销*/printf("从终点向前推,最短路径经过了: ");i = n-1; /*n-1就是终点的编号,本例中,n值为7*/while(i!=0) {printf(" %d",path[i]); /* 输出最短路径上前一个结点的编号*/ i = path[i]; /*从刚输出的结点,再循环向前倒推*/}printf("\n");return 0;
}
这篇关于C语言及程序设计进阶例程-28 动态规划法问题求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!