Liny_@NotePad

沉迷ACG中

动态规划求多段图单源最短路径

YOYO posted @ 2009年4月29日 08:11 in 【算法】与【数据结构】 with tags 动态规划 单源最短路径 , 7807 阅读

从终点n-1开始，直到顶点0，对每个点：
遍历其所能达到的各个结点，判断通过该结点访问终点的路径是否小于当前能找到的最短距离，是则更新，否则不变。
  最后，顶点0找到的最短距离必然是该点到达终点n-1的最短距离。
* 局限性：本程序只能求从顶点0到顶点n-1的最短路，且只能从编号较小的点访问编号较大的点。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 50        //  最多顶点数
  5. #define MAX 9999        //      最大路径权
  6.  
  7. typedef struct NODE {   // 顶点结构
  8.         int v;        //        顶点的编号
  9.         int len;                        //      到顶点的距离
  10.         struct NODE *next;      //    下一个可到达点
  11. }Node;
  12.  
  13. int n;        //        顶点数
  14. Node node[N];      // 存储顶点到各点的距离
  15. int route[N];      // 存放顶点到终点最短路的路径
  16.  
  17. /*
  18. * 求多段图单源最短路径的DP解法
  19. *
  20. * 输入：n - 顶点数， mz[][] - 存放距离的邻接矩阵
  21. * 输出：cost[0] - 最短路长度， route[] - 顶点到终点最短路的路径
  22. */
  23. int dp(){
  24.         int cost[N], path[N];
  25.         int i;
  26.        
  27.         /* 初始化距离 */
  28.         cost[n-1] = 0;
  29.        
  30.         /* DP求解 */
  31.         for(i=n-2; i>=0; i--){
  32.                 cost[i] = MAX;      // 一开始不可到达
  33.                 Node* p = node[i].next;
  34.                 while(p){
  35.                         if(cost[p->v] + p->len < cost[i]){       // 如果这个走法比之前的消耗更小则更新
  36.                                 cost[i] = cost[p->v] + p->len;
  37.                                 path[i] = p->v;
  38.                         }
  39.                         p = p->next;
  40.                 }
  41.         }
  42.  
  43.         /* 计算最短路径 */
  44.         i = 1;
  45.         route[0] = 0;
  46.         while(route[i-1]!=n-1){
  47.                 route[i] = path[route[i-1]];
  48.                 i++;
  49.         }
  50.  
  51.         return cost[0];
  52. }
  53.  
  54.  
  55. int main(){
  56.         int i,j;
  57.         cin>>n; 
  58.  
  59.         /*      输入各个顶点所能到达的结点及对应权值（以0结束） */
  60.         for(i=0; i<n; i++){
  61.                 Node* p;
  62.                 while(cin>>j&&j!=0){
  63.                         p = new Node;
  64.                         p->v = j;
  65.                         cin>>p->len;
  66.                         p->next = node[i].next;
  67.                         node[i].next = p;
  68.                 }
  69.         }
  70.  
  71.         cout<<"顶点0到顶点"<<n-1<<"的距离是："<<dp()<<endl;
  72.  
  73.         /* 打印最短路径 */
  74.         cout<<"最短路径是：";
  75.         for(i=0; route[i] != n-1; i++)cout<<route[i]<<"->";
  76.         cout<<n-1<<endl;
  77.  
  78.         return 0;
  79. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter