Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3001
  • 博文数量: 4
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2017-07-24 14:42
文章分类
文章存档

2017年(4)

我的朋友
最近访客

分类: C/C++

2017-07-24 14:43:00


    Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
    Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,比如数据结构、图论、运筹学等。
   
1、算法思想
    令G = (V,E)为一个带权有向图,
把图中的顶点集合V分成两组,第一组为已求出最短路径的顶点集合S(初始时S中只有源节点,以后每求得一条最短路径,就将它对应的顶点加入到集合S中,直到全部顶点都加入到S中);第二组是未确定最短路径的顶点集合U。在加入过程中,总保持从源节点v到S中各顶点的最短路径长度不大于从源节点v到U中任何顶点的最短路径长度。
 
2、算法步骤
    (1)初始化时,S只含有源节点;
    (2)从U中选取一个距离v最小的顶点k加入S中(该选定的距离就是v到k的最短路径长度);
    (3)以k为新考虑的中间点,修改U中各顶点的距离;若从源节点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值是顶点k的距离加上k到u的距离;
    (4)重复步骤(2)和(3),直到所有顶点都包含在S中。
    具体图例与算法执行步骤:(就从A开始,到各节点的最短路径)。
     
    具体执行步骤如下图所示。
    
    PS:图片右下角是原作者的博客地址。
    
3、算法具体实现
     算法的具体实现如下所示。
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "io.h"
  4. #include "math.h"
  5. #include "time.h"

  6. #define OK 1
  7. #define ERROR 0
  8. #define TRUE 1
  9. #define FALSE 0

  10. #define MAXEDgE 20
  11. #define MAXVEX 20
  12. #define INFINITY 65535

  13. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */


  14. typedef struct
  15. {
  16.     int vexs[MAXVEX];
  17.     int arc[MAXVEX][MAXVEX];
  18.     int numVertexes, numEdges;
  19. }Mgraph;

  20. typedef int Patharc[MAXVEX];            /* 用于存储最短路径下标的数组 */
  21. typedef int ShortPathTable[MAXVEX];        /* 用于存储到各点最短路径的权值和 */


  22. void CreateMgraph(Mgraph *g)
  23. {
  24.     int i, j;

  25.     /* printf("请输入边数和顶点数:"); */
  26.     g->numEdges=16;
  27.     g->numVertexes=9;

  28.     for (i = 0; i < g->numVertexes; i++)/* 初始化图 */
  29.     {
  30.         g->vexs[i]=i;
  31.     }

  32.     for (i = 0; i < g->numVertexes; i++)/* 初始化图 */
  33.     {
  34.         for ( j = 0; j < g->numVertexes; j++)
  35.         {
  36.             if (i==j)
  37.                 g->arc[i][j]=0;
  38.             else
  39.                 g->arc[i][j] = g->arc[j][i] = INFINITY;
  40.         }
  41.     }

  42.     g->arc[0][1]=1;
  43.     g->arc[0][2]=5;
  44.     g->arc[1][2]=3;
  45.     g->arc[1][3]=7;
  46.     g->arc[1][4]=5;

  47.     g->arc[2][4]=1;
  48.     g->arc[2][5]=7;
  49.     g->arc[3][4]=2;
  50.     g->arc[3][6]=3;
  51.     g->arc[4][5]=3;

  52.     g->arc[4][6]=6;
  53.     g->arc[4][7]=9;
  54.     g->arc[5][7]=5;
  55.     g->arc[6][7]=2;
  56.     g->arc[6][8]=7;

  57.     g->arc[7][8]=4;


  58.     for(i = 0; i < g->numVertexes; i++)
  59.     {
  60.         for(j = i; j < g->numVertexes; j++)
  61.         {
  62.             g->arc[j][i] =g->arc[i][j];
  63.         }
  64.     }

  65. }

  66. /* Dijkstra算法,求有向网g的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */
  67. /* P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */
  68. void ShortestPath_Dijkstra(Mgraph g, int v0, Patharc *P, ShortPathTable *D)
  69. {
  70.     int v,w,k,min;
  71.     int final[MAXVEX];                    /* final[w]=1表示求得顶点v0至vw的最短路径 */
  72.     
  73.     /* 初始化数据 */
  74.     for(v=0; v<g.numVertexes; v++)        
  75.     {
  76.         final[v] = 0;                    /* 全部顶点初始化为未知最短路径状态 */
  77.         (*D)[v] = g.arc[v0][v];            /* 将与v0点有连线的顶点加上权值 */
  78.         (*P)[v] = 0;                    /* 初始化路径数组P为0 */
  79.     }

  80.     (*D)[v0] = 0;                        /* v0至v0路径为0 */
  81.     final[v0] = 1;                        /* v0至v0不需要求路径 */
  82.     
  83.     /* 开始主循环,每次求得v0到某个v顶点的最短路径 */
  84.     for(v=1; v<g.numVertexes; v++)
  85.     {
  86.         min=INFINITY;                    /* 当前所知离v0顶点的最近距离 */
  87.         for(w=0; w<g.numVertexes; w++) /* 寻找离v0最近的顶点 */
  88.         {
  89.             if(!final[w] && (*D)[w]<min)
  90.             {
  91.                 k=w;
  92.                 min = (*D)[w];            /* w顶点离v0顶点更近 */
  93.             }
  94.         }
  95.         final[k] = 1;                    /* 将目前找到的最近的顶点置为1 */

  96.         /* 修正当前最短路径及距离 */
  97.         for(w=0; w<g.numVertexes; w++)
  98.         {
  99.             /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
  100.             if(!final[w] && (min+g.arc[k][w]<(*D)[w]))
  101.             {
  102.                 /* 说明找到了更短的路径,修改D[w]和P[w] */
  103.                 (*D)[w] = min + g.arc[k][w]; /* 修改当前路径长度 */
  104.                 (*P)[w]=k;
  105.             }
  106.         }
  107.     }
  108. }

  109. int main(void)
  110. {
  111.     int i,j,v0;
  112.     Mgraph g;
  113.     Patharc P;
  114.     ShortPathTable D; /* 求某点到其余各点的最短路径 */
  115.     v0=0;
  116.     
  117.     CreateMgraph(&g);
  118.     
  119.     ShortestPath_Dijkstra(g, v0, &P, &D);

  120.     printf("最短路径倒序如下:\n");
  121.     for(i=1;i<g.numVertexes;++i)
  122.     {
  123.         printf("v%d - v%d : ",v0,i);
  124.         j=i;
  125.         while(P[j]!=0)
  126.         {
  127.             printf("%d ",P[j]);
  128.             j=P[j];
  129.         }
  130.         printf("\n");
  131.     }
  132.     printf("\n源点到各顶点的最短路径长度为:\n");
  133.     for(i=1;i<g.numVertexes;++i)
  134.         printf("v%d - v%d : %d \n",g.vexs[0],g.vexs[i],D[i]);
  135.     return 0;
  136. }








   








    
阅读(165) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:Linux启动过程详解

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册