专栏首页Urlteamacm-最短路径算法

acm-最短路径算法

能力有限,只是研究了两种fioyd和Dijkstra算法,还有一个BellmanFord得下次接触了,

floyd算法

部分内容参考 http://leon.cc.blogbus.com/logs/3629782.html

All-Pairs 的最短路径问题:所有点对之间的最短路径

Dijkstra算法是求单源最短路径的,那如果求图中所有点对的最短路径的话则有以下两种解法:

解法一:

以图中的每个顶点作为源点,调用Dijkstra算法,时间复杂度为O(n3);

解法二:

Floyd(弗洛伊德算法)更简洁,算法复杂度仍为O(n3)。

n 正如大多数教材中所讲到的,求单源点无负边最短路径用Dijkstra,而求所有点最短路径用Floyd。确实,我们将用到Floyd算法,但是,并不是说所有情况下Floyd都是最佳选择。

对于没有学过Floyd的人来说,在掌握了Dijkstra之后遇到All-Pairs最短路径问题的第一反应可能会是:计算所有点的单源点最短路径,不就可以得到所有点的最短路径了吗。简单得描述一下算法就是执行n次Dijkstra算法。

Floyd可以说是Warshall算法的扩展了,三个for循环便可以解决一个复杂的问题,应该说是十分经典的。从它的三层循环可以看出,它的复杂度是n3,除了在第二层for中加点判断可以略微提高效率,几乎没有其他办法再减少它的复杂度。

比较两种算法,不难得出以下的结论:对于稀疏的图,采用n次Dijkstra比较出色,对于茂密的图,可以使用Floyd算法。另外,Floyd可以处理带负边的图。 下面对Floyd算法进行介绍:

Floyd算法的基本思想:

可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,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之间的最短距离了。

Floyd算法的基本步骤:

定义n×n的方阵序列D-1, D0 , … Dn-1,

初始化: D-1=C

D-1[i][j]=边<i,j>的长度,表示初始的从i到j的最短路径长度,即它是从i到j的中间不经过其他中间点的最短路径。

迭代:设Dk-1已求出,如何得到Dk(0≤k≤n-1)?

Dk-1[i][j]表示从i到j的中间点不大于k-1的最短路径p:i…j,

考虑将顶点k加入路径p得到顶点序列q:i…k…j,

若q不是路径,则当前的最短路径仍是上一步结果:Dk[i][j]= Dk-1[i][j];

否则若q的长度小于p的长度,则用q取代p作为从i到j的最短路径。

因为q的两条子路径i…k和k…j皆是中间点不大于k-1的最短路径,所以从i到j中间点不大于k的最短路径长度为:

Dk[i][j]=min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }

Floyd算法实现: 可以用三个for循环把问题搞定了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的程序,但是仔细考虑的话,会发现是有问题的。 for(int i=0; i<n; i++) for(int j=0; j<n; j++) for(int k=0; k<n; k++) 问题出在我们太早的把i-k-j的距离确定下来了,假设一旦找到了i-p-j最短的距离后,i到j就相当处理完了,以后不会在改变了,一旦以后有使i到j的更短的距离时也不能再去更新了,所以结果一定是不对的。所以应当象下面一样来写程序:

for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; 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代码

#include &lt;stdio.h&gt;           
   #include &lt;limits.h&gt;         
   #include &lt;stdlib.h&gt;          
   #define   MAXSIZE   20      

   void  floyd(int [][MAXSIZE], int [][MAXSIZE], int);
   void  display_path(int [][MAXSIZE], int [][MAXSIZE], int);
   void  reverse(int [], int);
   void  readin(int [][MAXSIZE], int *);

   #define   MAXSUM(a, b)   (((a) != INT_MAX &amp;&amp; (b) != INT_MAX) ? \
                          ((a) + (b)) : INT_MAX)

   void floyd(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
   {
       int  i, j, k;
       for (i = 0; i &lt; n; i++)
           for (j = 0; j &lt; n; j++)
               path[i][j] = i;
       for (k = 0; k &lt; n; k++)
           for (i = 0; i &lt; n; i++)
               for (j = 0; j &lt; n; j++)
                    if (dist[i][j] &gt; MAXSUM(dist[i][k], dist[k][j]))
                    {
                         path[i][j] = path[k][j];
                         dist[i][j] = MAXSUM(dist[i][k], dist[k][j]);
                    }
   }

   void display_path(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
   {
       int  *chain;
       int  count;
       int  i, j, k;
       printf("\n\nOrigin-&gt;Dest   Dist   Path");
       printf(  "\n-----------------------------");
       chain = (int *) malloc(sizeof(int)*n);
       for (i = 0; i &lt; n; i++)
           for (j = 0; j &lt; n; j++)
           {
               if (i != j)
               {
                    printf("\n%6d-&gt;%d    ", i+1, j+1);
                    if (dist[i][j] == INT_MAX)
                         printf("  NA    ");
                    else
                    {
                         printf("%4d    ", dist[i][j]);
                         count = 0; 
                         k = j;
                         do
                         {
                             k = chain[count++] = path[i][k];
                         } while (i != k);
                         reverse(chain, count);
                         printf("%d", chain[0]+1);
                         for (k = 1; k &lt; count; k++)
                              printf("-&gt;%d", chain[k]+1);
                         printf("-&gt;%d", j+1);
                    }
               }
           }
       free(chain);           
   }

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

   void reverse(int x[], int n)
   {
       int  i, j, temp;
       for (i = 0, j = n-1; i &lt; j; i++, j--)
            SWAP(x[i], x[j]);
   }

   void readin(int dist[][MAXSIZE], int *number)
   {
       int  origin, dest, length, n;
       int  i, j;
       char line[100];
       gets(line);            
       sscanf(line, "%d", &amp;n);
       *number = n;
       for (i = 0; i &lt; n; i++)
       {
           for (j = 0; j &lt; n; j++)
                dist[i][j] = INT_MAX;
           dist[i][i] = 0;   
       }
       gets(line);            
       sscanf(line, "%d%d%d", &amp;origin, &amp;dest, &amp;length);
       while (origin != 0 &amp;&amp; dest != 0 &amp;&amp; length != 0)
       {
          dist[origin-1][dest-1] = length;
          gets(line);       
          sscanf(line, "%d%d%d", &amp;origin, &amp;dest, &amp;length);
       }
   }
    /// 测试程序如下所示:
   int main(void)
   {
       int dist[MAXSIZE][MAXSIZE];
       int path[MAXSIZE][MAXSIZE];
       int n;
       printf("\nInput the path information:");
       printf("\n----------------------------\n");
       readin(dist, &amp;n);
       floyd(dist, path, n);
       display_path(dist, path, n);
       getchar();
   }
     其中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-&gt;Dest      Dist          Path
  ----------------------------------------------
        1-&gt;2             5          1-&gt;2
        1-&gt;3            15          1-&gt;2-&gt;4-&gt;3
        1-&gt;4            10          1-&gt;2-&gt;4
        2-&gt;1            20          2-&gt;4-&gt;1
        2-&gt;3            10          2-&gt;4-&gt;3
        2-&gt;4             5          2-&gt;4
        3-&gt;1            30          3-&gt;1
        3-&gt;2            35          3-&gt;1-&gt;2
        3-&gt;4            15          3-&gt;4
        4-&gt;1            15          4-&gt;1
        4-&gt;2            20          4-&gt;1-&gt;2
        4-&gt;3             5          4-&gt;3
Dijkstra算法

一种最短路径算法,用于计算一个节点到其它所有节点的最短路径,动态路由协议OSPF中就用到了Dijkstra算法来为路由计算最短路径。

算法本身并不是按照我们的正常思维习惯,我们一般会,从原点遍历所有与之相连的节点,找到最短路径,再从最短路径上的那个点遍历与之相连的所有其它点(原点除外),然后依次类推。这样做虽然可以算出一个树形,但是在大多数情况下,这种算法会产生很多次优路径,也就是说非最短路径。

Dijkstra算法的大概过程:

假设有两个集合或者说两个表,表A和表B

表A表示生成路径,表B表示最后确定的路径

1.从原点出发,遍历检查所有与之相连的节点,将原点和这些节点存放到表A中,并记录下两节点之间的代价。

2.将代价最小的代价值和这两节点移动到表B中(其中一个是原点)。

3.把这个节点所连接的子节点找出,放入到表A中,算出子节点到原点的代价

4.重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。

维基百科中还有另一种说法,Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合,而边的权重则由权重函数w: E → [0, ∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。

Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因

Dijkstra算法

自己写的每次更新后的所对应的一些顶点和距离的变化

S U

{1} {2,3,4,5,6} {0,2,4,∞,∞,∞}

{1,2} {3,4,5,6} {0,2,3,6,4,∞}

{1,2,3} {4,5,6} {0,2,3,6,4,∞}

{1,2,3,5} {4,6} {0,2,3,6,4,6}

{1,2,3,5,4} {6} {0,2,3,6,4,6}

{1,2,3,5,4,6} {} {0,2,3,6,4,6}

原创文章,转载请注明: 转载自URl-team

本文链接地址: acm-最短路径算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 初识数据库

    将数据看做一个二维表格,数据可以通过行号+列号唯一确定,其数据结构类似 Excel 表;

    村雨
  • 【简单的CV】1.4 图片导入与像素值

    在学习导入图片和像素值之前,我们先讨论一个问题,为什么电脑中图片文件的格式会有JPG/PNG/BMP/....等不同格式呢?

    EdenChen
  • 深入学习 Node.js Buffer

    ArrayBuffer 对象用来表示通用的、固定长度的原始二进制数据缓冲区。ArrayBuffer 不能直接操作,而是要通过类型数组对象 或 DataView ...

    semlinker
  • 重温 ES6 Symbol

    1.Symbol 通过工厂函数创建,不能以 new 的方式创建,所以使用 instanceof 运算符返回的结果为 false

    semlinker
  • 一份不可多得的 Lombok 学习指南

    Lombok 是一款 Java 开发插件,使得 Java 开发者可以通过其定义的一些注解来消除业务工程中冗长和繁琐的代码,尤其对于简单的 Java 模型对象(P...

    semlinker
  • 分布式唯一 ID 之 Snowflake 算法

    Snowflake(雪花) 是一项服务,用于为 Twitter 内的对象(推文,直接消息,用户,集合,列表等)生成唯一的 ID。这些 IDs 是唯一的 64 位...

    semlinker
  • 算法图解 第1章 算法简介

    一种算法,输入是一个有序的元素列表,如果查找的元素包含在列表中,则二分查找返回其位置,否则返回null;

    村雨
  • Redis Cluster

    Redis Cluster是Redis的分布式解决方案。当遇到内存、并发、流量等瓶颈时,就可以采用Cluster架构达到负载均衡目的。因为Redis Clust...

    吉林乌拉
  • 简单的CV(计算机视觉)学习

    计算机图形学(Computer Graphics,简称CG),计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示...

    EdenChen
  • 深入学习 Node.js Module

    Node.js 遵循 CommonJS规范,该规范的核心思想是允许模块通过 require 方法来同步加载所要依赖的其他模块,然后通过 exports 或 mo...

    semlinker

扫码关注云+社区

领取腾讯云代金券