动态规划——多段图的最短路径

本文主要是介绍动态规划——多段图的最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

源码

#include<stdio.h>
#include<stdlib.h>
const int INF = 1000;
const int N = 100;//图的最大结点数为100
int arc[N][N];//图的代价矩阵
int cost[N];//存储路径长度
int path[N];//路径
int ClosetPath(int n) {int i,j,temp;for(i=1; i<n; i++) {cost[i]=INF;path[i]=-1;}cost[0]=0;path[0]=-1;//起点for(j=1; j<n; j++) {for(i=j-1; i>=0; i--) {if(arc[i][j]+cost[i]<cost[j]) {cost[j]=arc[i][j]+cost[i];path[j]=i;}}}return cost[n-1];
}
void printPath(int i) {if(i!=-1) {printPath(path[i]);printf("%d-",i);}
}
int main() {int i,j,n,m;//printf("请输入结点个数和边个数：");//scanf("%d%d",&n,&m);n=10;m=18;for(i=0; i<n; i++)for(j=0; j<n; j++)arc[i][j]=INF;
// for(i=0;i<m;i++){
//  int a,b,c;
//  printf("请输入边的两个顶点计权重：");
//  scanf("%d%d%d",&a,&b,&c);
//  arc[a][b]=c;
// }arc[0][1]=4;arc[0][2]=2;arc[0][3]=3;arc[1][4]=9;arc[1][5]=8;arc[2][4]=6;arc[2][5]=7;arc[2][6]=8;arc[3][5]=4;arc[3][6]=7;arc[4][7]=5;arc[4][8]=6;arc[5][7]=8;arc[5][8]=6;arc[6][7]=6;arc[6][8]=5;arc[7][9]=7;arc[8][9]=3;int min = ClosetPath(n);for(i=0;i<n;i++)printf("%3d",path[i]);printf("\n最短路径为：");printPath(path[n-1]);printf("%d",n-1);printf("\n最短距离：%d",min);return 0;
}

这篇关于动态规划——多段图的最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---