Liny_@NotePad

沉迷ACG中

贪心法求解单源最短路径问题

YOYO posted @ 2009年4月29日 08:08 in 【算法】与【数据结构】 with tags 贪心 dijkstra 单源最短路径 , 3152 阅读

虽说之前贴了模版 = = 但还是按照老师的格式写一下……

每次找到距离源点最接近且未被访问的点，对该点能到达的所有结点遍历比较经过该点中转后的距离是否小于之前计算的最短距离，是则更新该结点距离（若之前没访问过还要置其访问标记为真）。最多查找n-1次各遍历过一遍后即可得出最终解。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. /* 邻接顶点数据结构 */
  5. typedef struct adj_list{
  6.         int v_num;                        // 邻接顶点编号
  7.         float len;                        // 邻接定点与该顶点的距离
  8.         struct adj_list *next;  //        下一个邻接顶点
  9. }NODE;
  10.  
  11. #define MAX_FLOAT_NUM 3.14E38f  //        最大的浮点型
  12. #define N 50                //  数组最多支持顶点数
  13.  
  14. /*************************************************************
  15. * dijkstra算法
  16. *
  17. * 输入：有向图的邻接表头结点node[]，顶点个数n，源节点u
  18. * 输出：源节点到各个结点的距离d[]及该最短路径前一顶点编号p[]
  19. *************************************************************/
  20. void dijkstra(NODE node[], int n, int u, float d[], int p[]){
  21.         float temp;
  22.         int i,j,t;
  23.         bool *s = new bool[n];    //       标记该点是否被访问过
  24.         NODE *pnode;
  25.  
  26.         /* 初始化 */
  27.         for( i=0; i<n; i++){
  28.                 d[i] = MAX_FLOAT_NUM;
  29.                 s[i] = false;
  30.                 p[i] = -1;
  31.         }
  32.  
  33.         if(!(pnode = node[u].next) ){      // 若源点与其他点都不相连则退出
  34.                 return;
  35.         }
  36.  
  37.         while(pnode){            // 令所有与源点相连的结点距离为预置的距离
  38.                 d[pnode->v_num] = pnode->len;
  39.                 p[pnode->v_num] = u;
  40.                 pnode = pnode->next;
  41.         }
  42.  
  43.         d[u] = 0;                                          //     置到源点自身距离为0
  44.         s[u] = true;                        //  置源点自身已访问
  45.  
  46.         for( i=1; i<n; i++){                //  遍历各个结点
  47.                 temp = MAX_FLOAT_NUM;
  48.                 t = u;              //        置t为源点
  49.                 for( j=0; j<n; j++){
  50.                         if(!s[j]&&d[j]<temp){   // 寻找距离源点最接近的、尚未被访问到的点
  51.                                 t = j;
  52.                                 temp = d[j];
  53.                         }
  54.                 }
  55.                 if(t==u){                                   //     若t依然为源点，则表示没找到：退出循环
  56.                         break;
  57.                 }
  58.                 s[t] = true;                    //  否则标记该结点访问为真
  59.  
  60.                 pnode = node[t].next;         // 指向该节点的邻接结点
  61.                 while(pnode){               // 若该结点未被访问过且当前源点到该点的最短距离大于（源点到t点的距离与t点到该点的距离之和）
  62.                         if(!s[pnode->v_num] && d[pnode->v_num] > d[t] + pnode->len ){
  63.                                 d[pnode->v_num] = d[t] + pnode->len;    //  更新该点最短距离
  64.                                 p[pnode->v_num] = t;    //  更新前置结点
  65.                         }
  66.                         pnode = pnode->next;        //  继续遍历下一结点
  67.                 }
  68.         }
  69.  
  70.         delete s;
  71. }
  72.  
  73. /******************************
  74. * 递归打印最短路径
  75. ******************************/
  76. void printWay(int i, int p[]){
  77.         if(p[i]==-1)return;
  78.         printWay(p[i], p);
  79.         cout<<"->"<<char(i+65);
  80. }
  81.  
  82. /* 打印换行间隔符 */
  83. void println(){
  84.         cout<<"------------------------------------------------"<<endl;
  85. }
  86.  
  87. int main(){
  88.         NODE node[N];
  89.         float d[N];
  90.         int p[N];
  91.         int n;
  92.         int u;
  93.         int i,v;
  94.         NODE *pnode;
  95.  
  96.         /* 输入开始 */
  97.         cout<<"请输入顶点个数：";
  98.         cin>>n;
  99.  
  100.         cout<<"请输入源顶点u编号（0<u<="<<n<<"）：";
  101.         cin>>u; 
  102.         u--;
  103.  
  104.         cout<<"请输入各个点到其他点的距离（输入顶点编号 距离，编号输入0表示结束）："<<endl;
  105.         for( i=0; i<n; i++){
  106.                 cout<<"顶点"<<char(65+i)<<"：";
  107.                 node[i] = *(new NODE);      //        创建新结点
  108.                 node[i].v_num = i;                        //    顶点编号
  109.                 node[i].len = 0;                                //      距离自身为0
  110.                 node[i].next = NULL;            //  先不给定下一邻接点
  111.                 while(cin>>v&&v>0){          //   继续输入，当输入小于0时表示输入结束：
  112.                         pnode = new NODE;                     //     创建新结点
  113.                         pnode->v_num = v-1;               //   结点编号为输入的编号-1（输入的编号从1开始）
  114.                         cin>>(pnode->len);                  //    输入结点到该点的距离
  115.                         pnode->next = node[i].next;     //   将结点插入表中
  116.                         node[i].next = pnode;
  117.                 }
  118.         }
  119.         /* 输入结束 */
  120.  
  121.         /* 执行dijkstra算法计算最短路 */
  122.         dijkstra(node, n, u, d, p);
  123.  
  124.         /* 输出开始 */
  125.         println();
  126.         for( i=0; i<n; i++){
  127.                 if(u==i||d[i]==MAX_FLOAT_NUM)continue;  //        当结点为源点或结点不可到达时略过
  128.                 cout<<char(u+65)<<"距离"<<char(i+65)<<"结点最短距离："<<d[i]<<endl;
  129.                 cout<<"路径："<<char(u+65);
  130.                 printWay(i, p);     //       递归打印最短路径
  131.                 cout<<endl;
  132.                 println();
  133.         }
  134.         /* 输出结束 */
  135.        
  136.         return 0;
  137. }
Small_feed 评论 (0)

登录 *


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