设为首页收藏本站联系我们

声振论坛

 找回密码
 我要加入

QQ登录

只需一步，快速开始

声振论坛 › 展示 ›基础理论 › 查看内容

路径优化的Floyd,dijkstra,A*算法的matlab代码

2012-10-24 15:27| 发布者: aspen| 查看: 5163| 评论: 0|原作者: assist|来自: 振动论坛

摘要: 路径优化的Floyd,dijkstra,A*算法的matlab代码
Floyd最短路径算法
2006-10-20, by leon_jlu
     在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层的时候好像也遇到过这个问题，记不请了... 但是书本上一律采取的是Dijkstra算法，通过Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味，采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下：
      如果有一个矩阵D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序，通过这个距离矩阵D，把任意两个城市之间的最短与其行径的路径找出来。
     我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的话，会发现是有问题的。
  1.                      for(int i=0; i
  2.                            for(int j=0; j
  3.                                 for(int k=0; k
复制代码
问题出在我们太早的把i-k-j的距离确定下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序：
  1.                     for(int k=0; k
  2.                          for(int i=0; i
  3.                               for(int j=0; j
复制代码
这样作的意义在于固定了k，把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个k，这样就不会有问题了，看来多层循环的时候，我们一定要当心，否则很容易就弄错了。
     接下来就要看一看如何找出最短路径所行经的城市了，这里要用到另一个矩阵P，它的定义是这样的：p(ij)的值如果为p，就表示i到j的最短行经为i->...->p->j，也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后，要找最短路径就轻而易举了。对于i到j而言找出p(ij)，令为p，就知道了路径i->...->p->j；再去找p(ip)，如果值为q，i到p的最短路径为i->...->q->p；再去找p(iq)，如果值为r，i到q的最短路径为i->...->r->q；所以一再反复，到了某个p(it)的值为i时，就表示i到t的最短路径为i->t，就会的到答案了，i到j的最短行径为i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。
     但是，如何动态的回填P矩阵的值呢？回想一下，当d(ij)>d(ik)+d(kj)时，就要让i到j的最短路径改为走i->...->k->...->j这一条路，但是d(kj)的值是已知的，换句话说，就是k->...->j这条路是已知的，所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的，当然，因为要改走i->...->k->...->j这一条路，j的上一个城市正好是p(kj)。所以一旦发现d(ij)>d(ik)+d(kj)，就把p(kj)存入p(ij)。
   下面是具体的C代码：
  1.    #include            
  2.    #include            
  3.    #include            
  4.    #define   MAXSIZE   20        

  6.    void  floyd(int [][MAXSIZE], int [][MAXSIZE], int);
  7.    void  display_path(int [][MAXSIZE], int [][MAXSIZE], int);
  8.    void  reverse(int [], int);
  9.    void  readin(int [][MAXSIZE], int *);

  11.    #define   MAXSUM(a, b)   (((a) != INT_MAX && (b) != INT_MAX) ? \
  12.                           ((a) + (b)) : INT_MAX)

  14.    void floyd(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
  15.    {
  16.        int  i, j, k;
  17.        for (i = 0; i < n; i++)  
  18.            for (j = 0; j < n; j++)
  19.                path[i][j] = i;
  20.        for (k = 0; k < n; k++)  
  21.            for (i = 0; i < n; i++)
  22.                for (j = 0; j < n; j++)  
  23.                     if (dist[i][j] > MAXSUM(dist[i][k], dist[k][j]))
  24.                     {
  25.                          path[i][j] = path[k][j];
  26.                          dist[i][j] = MAXSUM(dist[i][k], dist[k][j]);
  27.                     }
  28.    }

  30.    void display_path(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
  31.    {
  32.        int  *chain;
  33.        int  count;
  34.        int  i, j, k;
  35.        printf("\n\nOrigin->Dest   Dist   Path");
  36.        printf(  "\n-----------------------------");
  37.        chain = (int *) malloc(sizeof(int)*n);
  38.        for (i = 0; i < n; i++)
  39.            for (j = 0; j < n; j++)
  40.            {
  41.                if (i != j)
  42.                {  
  43.                     printf("\n%6d->%d    ", i+1, j+1);
  44.                     if (dist[i][j] == INT_MAX)
  45.                          printf("  NA    ");
  46.                     else
  47.                     {
  48.                          printf("%4d    ", dist[i][j]);
  49.                          count = 0;   
  50.                          k = j;
  51.                          do
  52.                          {
  53.                              k = chain[count++] = path[i][k];
  54.                          } while (i != k);
  55.                          reverse(chain, count);
  56.                          printf("%d", chain[0]+1);
  57.                          for (k = 1; k < count; k++)
  58.                               printf("->%d", chain[k]+1);
  59.                          printf("->%d", j+1);
  60.                     }
  61.                }
  62.            }
  63.        free(chain);            
  64.    }

  66.    #define SWAP(a, b)  { temp = a; a = b; b = temp; }

  68.    void reverse(int x[], int n)
  69.    {
  70.        int  i, j, temp;
  71.        for (i = 0, j = n-1; i < j; i++, j--)
  72.             SWAP(x[i], x[j]);
  73.    }

  75.    void readin(int dist[][MAXSIZE], int *number)
  76.    {
  77.        int  origin, dest, length, n;
  78.        int  i, j;
  79.        char line[100];
  80.        gets(line);              
  81.        sscanf(line, "%d", &n);
  82.        *number = n;
  83.        for (i = 0; i < n; i++)
  84.        {
  85.            for (j = 0; j < n; j++)
  86.                 dist[i][j] = INT_MAX;
  87.            dist[i][i] = 0;     
  88.        }
  89.        gets(line);              
  90.        sscanf(line, "%d%d%d", &origin, &dest, &length);
  91.        while (origin != 0 && dest != 0 && length != 0)
  92.        {
  93.           dist[origin-1][dest-1] = length;
  94.           gets(line);         
  95.           sscanf(line, "%d%d%d", &origin, &dest, &length);
  96.        }
  97.    }
复制代码
测试程序如下所示：
  1.    int main(void)
  2.    {
  3.        int dist[MAXSIZE][MAXSIZE];
  4.        int path[MAXSIZE][MAXSIZE];
  5.        int n;
  6.        printf("\nInput the path information:");
  7.        printf("\n----------------------------\n");
  8.        readin(dist, &n);
  9.        floyd(dist, path, n);
  10.        display_path(dist, path, n);
  11.        getchar();
  12.    }
复制代码
其中readin函数规定了输入的格式，第一列是指出有多少个城市；第二列以后每行三个数；第一个和第二个是一条路径的起点和终点，第三个数是路径的长度，最后以三个0作为输入结束条件。下面是一个输入的例子：
              Input the path information:
            --------------------------------------
              4
              1          2          5
              2          1          50
              2          3          15
              2          4          5
              3          1          30
              3          4          15
              4          1          15
              4          3          5
              0          0          0

   对应的输出结果为：
     Origin->Dest      Dist          Path
  ----------------------------------------------
        1->2             5           1->2
        1->3            15          1->2->4->3
        1->4            10          1->2->4
        2->1            20          2->4->1
        2->3            10          2->4->3
        2->4             5           2->4
        3->1            30          3->1
        3->2            35          3->1->2
        3->4            15          3->4
        4->1            15          4->1
        4->2            20          4->1->2
        4->3             5           4->3

本文内容由 assist 提供

12345下一页
收藏 分享 邀请

最新评论

相关分类

下级分类

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-5-4 21:22 , Processed in 0.032817 second(s), 15 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

返回顶部