动态规划 最短路径

#include<stdio.h> #include<stdlib.h> #define NODENUM 7 #define INF 255 static char node[NODENUM] = {'A','B','C','D','E','F','G'}; void PrintWay(int way[],int len); int getMinRoutineVal(int array[NODENUM][NODENUM],int len);//数组作为参数时要指明长度 int main() { int minval; int array[NODENUM][NODENUM]= { /* A B C D E F G*/ /*A*/ {0, 5, 2, 0, 0, 0, 0}, // B -3- D /*B*/ {0, 0, 0, 3, 2, 0, 0}, // / / /4 /*C*/ {0, 0, 0, 0, 7, 4, 0}, // /5 2/ /_ /*D*/ {0, 0, 0, 0, 0, 0, 4}, // A E -3- G /*E*/ {0 ,0, 0, 0, 0, 0, 3}, // /2 / / /*F*/ {0, 0, 0, 0, 0, 0, 5}, // / /7 /5 /*G*/ {0, 0, 0, 0, 0, 0, 0} // C -4- F }; // int sr[NODENUM] = {0};//存放各节点最短路径 minval = getMinRoutineVal(array,NODENUM); printf("%d", minval); getch(); return 0; } int getMinRoutineVal(int array[NODENUM][NODENUM],int len) { int ret=0; int sr[NODENUM]; int way[NODENUM]; int i,j,temp; sr[len-1] = 0; way[len-1] = len-1; for(i=len-2; i>=0; i--) //计算每点的最小routine value.从根向顶层遍历 { sr[i] = INF; way[i] = 0; for(j=i+1; j<len; j++) { if(array[i][j] != 0) { temp = sr[j]+array[i][j]; if(temp < sr[i]) { sr[i] = temp; way[i] = j; } } } } PrintWay(way,NODENUM); ret = sr[0]; return ret; } void PrintWay(int way[],int len) //打印路径 { int i=0; while(i != len-1) { printf("%c/n",node[i]); i = way[i]; } printf("%c/n",node[i]); }