布局布线算法

                                                            By 白叶Stuart

布局布线算法详细介绍

FPGA 的布局是把逻辑子电路与 CLB 单元一一对应的分布在 FPGA 芯片上，但是FPGA 是有规格的芯片，电路的需求是多种多样的，当把电路分布到 FPGA芯片上时，电路往往不会占满整个芯片，电路中的子电路与芯片上 CLB 的映射关系，关系到电路的最优化布局。布局的工作就是确定电路网表中的逻辑块在芯片中的位置，其结果对布线及整个流程有着至关重要的影响。

布局阶段的输入是一组模块及其引线端信息和网表。模块可分为"硬模块"和"软模块"。硬模块内的电路版图已经完成，模块的形状大小已知。而软模块则需要在布局阶段确定其形状和大小。

通常所说的布局需要规划的是硬模块，只需确立其在芯片上的位置。但当模块中存在软模块时，布局问题就成为了"布图规划"问题。在"布图规划"问题中，我们除了需要确定所有模块的位置之外，还需要对软模块的形状和大小进行确定，通常完成布图规划后还需要确定软模块上引线端的分配。

How?

什么是NP问题？

布局问题是多目标优化问题，多个目标之间也不是完全独立的，因此布局问题也是 NP-hard问题。

以下是一些名词解释：

多项式级的复杂度: O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置。

非多项式级的复杂度：O(a^n)和O(n!)等，计算机往往不能承受所需要的计算量。

P类问题：在多项式时间内可解的问题。

NP问题（Nondeterminism Polynomial）：在多项式时间内"可验证"的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。

NP-complete问题：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：

1.一个NP问题；

2.所有的NP问题都可以约化到它。

NP-Hard问题: 即多项式复杂程度的非确定性问题。 它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是他不一定是一个NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

怎样面对NP问题？

旅行商问题 (traveling salesman problem)，是最具有代表性的NP-hard问题之一。假设一个推销员需要从香港出发，经过广州，北京，上海等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 C 块钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。若欲求精确解，时间复杂度为（n-1)!/2 。在n=20时，需要计算6×10¹⁶次，假如计算机每秒计算一亿次，需要计算20年。目前来说，尚未有一种能够精确解决NP问题的方法出现，我们主要通过近似方法解决NP问题。

在面对此类问题时，有以下几种常用的方法。

1. 限制问题的范围

例如求最小树时只求最小生成树，即限制树的交叉点只能是原顶点。求最小生成树是在多项式时间内可以解出来的，但此近似方法的问题在于最小生成树不一定是最小树。

1. 限制问题的规模

如上所提旅行商问题，n=20时需要计算20年，但当n=10时，仅需计算约181440次，所需时间约为0.0018秒。因此，分区优化是一种比较有效的解决旅行商问题的方法。

如图所示，将整个区域划分为4个分区，由于分区降低了问题规模，使得有可能对每个分区进行精确求解，求解完之后再将每个分区看作一个节点进行整体求解。

1. 分枝定界法

分枝定界法分为两个部分："分枝"与"定界"。"分枝"意即将原始的大问题分成多个子问题求解。"定界"意即设置上下界，在求解中发现当前求解的值超过所设上下界时即视作非最优解，不再求解。以旅行商问题为例：

1. 可首先选择一条所经城市编号顺序依次为1,2,3...18,19,20的路径。计算此路径之长度，其值作为下界。
2. 更改末尾两城顺序，又得一路径，与之前所得下界比较，取其小者为新下界。再依次类推，分别更改 后3,后4...直至后19个城市顺序。求解中，若目前
3. 取除1号城市外的另一城市作为路径首个城市。执行第一步和第二步，直至所有城市都当过路径第一个城市。

分枝定界法的关键值在最坏情况下依然需要枚举所有方案,常用的方法是使用启发式算法求得近似解，以这个近似解作为分枝定界法的界限

1. 启发式算法

启发式算法是目前求解NP-hard问题最常用的方法，它往往抓住问题的主干来构造算法，忽略次要因素，以此降低算法复杂度。启发式算法拥有启发函数，它被用来估算当前state和 目标state之间的距离，用于路径决策。 也就是说，该函数直接决定了寻找路径的快慢和准确度。以旅行商问题为例，有两种启发式算法：

1. 最近邻法。它属于贪婪算法，将离当前城市最近的城市作为访问目标。以每一步的视角来看，它做出了当前最优解，但以整体而言则未必。若精确解结果为T₀，此算法得出的近似解为T₁，有：

    T₀<(log2(n)+1)*T₁/2

    此算法时间复杂度为（n-1)(n-2)/2。

1. 最近插入法。思路是在尚未访问的城市中，离当前已经走过的所有城市最近的城市作为下一步访问的城市,设本算法所得近似解为T₂,有

    T₂<2T₀

此算法的时间复杂度为O（n²）。

对于启发式算法，一个良好的初始布局能大大减少计算量。

准备工作

优化的目标是：

1) 确保布线工具能够完成布线。

2) 最小化关键路径的延时。

3) 是芯片尽量密集。

这三个目标是是布局的主要最优化方向，有时考虑到硬件的特性我们还会考虑最小化功耗和最小化信号间的串扰。

目前的布局算法研究中通常是使用更为直观量化的目标准则，来取代以上这些感性的目标，使算法更能准确的解决问题，目前的布局目标通常是：

1. 使子电路间的互连线总长度最小。
2. 关键网络的是时序延时符合要求。
3. 使互连线的拥塞度最小，以利于布线成功。

这些目标并不是相互独立的问题，它们每两个之间都会存在一定的关系，在布局的时候并不是对每个目标都实现最好的解决，这是达不到的，因此需要对三个目标进行折中，取得最好的结果。

    需要注意的是，根据布局对象的不同，目标也会有区别。对于门阵列模式和PCB的布局，其目的是达到较高的布通率。而对于标准单元的布局，目标一般为芯片总面积最小或者总连线长度最小。

数据结构

数据结构决定了版图以什么形式存储在计算机中，不同的数据结构进行查找和删除等操作消耗的时间差别极大。集成电路中常见数据结构的有链表、Bin、k-D树、四叉树和角勾链等。

角勾链

角勾链，作为一种数据结构在无网格区域布线中得到了非常广泛的应用。

有别于链表、Bin、k-D树、四叉树等数据结构的是，角勾链:

1. 显式地表达空区域。
2. 相邻模块间用指针连接。点查找和模块插入操作的复杂度均为 。

这种组织方式可产生用于搜索，创建，删除，拉伸和压缩的快速算法（O（n）或更短）。代价是角勾链所需要的存储空间大约是最简单表示的三倍。

如图所示，角勾链中一个模块有四个指针，分别指向上下左右四个方向的相邻模块。需要注意的是，角勾链要求将空区域分割为砖，通过左右指针在水平方向作分割，直至遇到实方块或版图边界。这种方法使得空砖在水平方向尽可能长且分割方式唯一。

分割实例如上所示，灰色方块代表已占用。空砖水平方向尽可能扩展，分割方式唯一。作为一种数据结构，接下来我们介绍角勾链的一些操作算法。返回

1. 点查找

   给定终点D和起点S，找出一条由S到D并且经过的砖数量最小的路径。假设点D坐标(x1,y1)，算法流程如下：

2. 通过rt和lb指针实现上下移动，直到找到一个纵向坐标包含y1的砖。
3. 通过tr和bl指针实现左右移动，直到找到一个横向坐标包含x1的砖。
4. 若在第二步中，直至越过坐标x1也未能找到包含点D的砖，则返回第一步重新进行操作。之所以会出现这种情况，是因为版图布局如下图，有多个砖包含了目标纵坐标。

    

   

   在角勾链中。点查找最坏情况下复杂度为O(n)，平均查找时间为)，n为方块数。

5. 邻接查找

   给定一砖，查找所有与它的某一边相邻接的砖。

   1. 从起始砖需要被查找的那条边的指针开始。例如若查找右边邻接，则从tr指针开始。
   2. 找到与其右边界相邻的位于最上方的砖，然后沿着该砖的lb指针向下查找。（这里以查找右边界为例，查找其他边时不必从上到下。事实上，只需要从边的一端查找到边的另一端即可）
   3. 遇到一个纵向范围超过起始砖纵向范围的砖，查找结束。

    

6. 区域搜索

   给定一个区域，判断该区域内是否有实砖（也就是已经占用的区域）存在。流程如下：

   1. 找到给定区域左上角的砖。
   2. 若上一步中找到的砖是一个空砖，且其右边界也在此区域内，则其右边界相邻的模块必定是一个实砖。因为角勾链的空砖水平方向尽可能扩展，直至遇到实砖或者版图边界才停止。
   3. 若在第二步中找到一个实砖，则查找结束。否则，通过lb指针向下和tr指针向右走到与该区域右边界接触的方块中。
   4. 重复第二步与第三步（注意方向需相反），直到找到一个实砖或者该区域被全部搜索完为止。
7. 遍历砖

   给定一个区域们，找到所有与此区域相交的砖。这里类似深度优先搜索：

   1. 找到给定区域左上角的砖，从左向右遍历砖直至遇到边界。
   2. 对于遍历到的每个砖：

      若此砖右边界在区域之外，结束;否则，使用邻接查找算法访问所有与当前方块右边界相邻接的砖。若 （邻接砖的左下角与当前砖邻接，如下图当前砖1邻接砖2）或者（邻接砖被区域的下边界切断，如下图当前砖7邻接砖8），则重复执行第二步——访问该邻接砖的邻接砖。

      

8. 模块建立

   当需要在版图中某个位置建立一个已知大小的模块（也即实砖）时，流程如下：

   1. 利用区域搜索算法查看指定区域是否可建立（即是否为空砖）。
   2. 找到新模块应占据区域的上下左右四个边界所属的空砖（最多三个，最少一个）。
   3. 分割第二步中找到的空砖，并更新与新模块相邻接的砖的指针。
9. 模块删除

   即删除版图上指定位置的模块。

   1. 将指定模块改为空砖。
   2. 水平合并。即分别对该空砖左右边界进行邻接查找，对于每一个邻接砖，通过分割邻接砖或者分割当前空砖的方式，使邻接砖和空砖具有完全一致的共同垂直边，然后对二者进行水平合并，并更改他们的相邻砖的指针。
   3. 垂直合并。在水平合并完成后，若上下边界的相邻空砖与当前空砖具有相同的水平边界，并且垂直边界也对齐相接（即合并之后仍然是一个砖），那么就对相邻砖和当前空砖进行合并，并更新他们的相邻砖的指针。

                                       返回

    

   目标函数

       不同的芯片布局模式选取的目标函数也有所不同，较为常用的有以下三种：

   1. 基于连线总长的目标

      目标函数为

      其中为连线总长，为线网长度估计值，N为所有线网集合，目标是使连线总长最小。

      一般可以在标准单元和BBL模式布局中采取本目标函数，因为此时连线总长最短基本等同于芯片面积最小。但在门阵列此类固定芯片布局中，由于通道数目固定，容易出现某些区域连线过于密集从而无法布通的情况。

       

   2. 基于割线的目标

   此法有两种目标函数。

   1. 使最大切割数目最小

   其中是x=时切割线和线网的交点数目，是y=时切割线和线网的交点数目，这两个数字越大，代表通道越拥挤。X(P)和Y(P)分别代表水平和垂直方向的最大切割线数目。交点布局目标就是使他们最小化，由此使线网尽可能均匀分配。

   

    

   

   1. 使总切割线数目最小

   布局目标是使T（P），也即总连线长度最短。

   布线容量与最大割线数之差代表可布性，差值越大，可布性越好。

    

   1. 基于最大密度最小的目标

   定义局部密度为：

           为区域e_i中的线网数目，为区域e_i中的通道容量。

           定义最大密度为：

           布局目标是使D(P)最小化，即使线网均匀分配，提高布通率。

           虽然最大密度最小化和最多割线最小化的原理相似，但是对于像门阵列这样通道固    定的芯片，最大密度最小化的目标函数更能反映布通率。

    

   1. 复合目标函数

   以上三种目标函数也可复合成目标函数，如：

   通过选择不同的q值，可以让此函数分别侧重考虑均匀分配和总连线长度。

    

   线长估计

       如前所述，一些目标函数需要用到连线长度，并且在优化时延时也需要用到线长。但是，真正准确的线长只有在布线完成后才能得出，在此之前若要用到线长，就需要进行估算。计算线长主要有最小斯坦纳树、最小链、源到漏端最小连接、完全图、边界框、半周长、二次线长、单树干斯坦纳树九种方法。前三种方法必须在构造完他们对应的布线树后才能计算线长，这在布局阶段比较困难。下面介绍三种具有代表性的线长估计算法。

10. 最小斯坦纳树

    给定一个连通图，图上的顶点分为两类： 必要顶点和斯坦纳顶点。现在，你需    要找到一棵边权值和最小的树，覆盖掉所有的必要顶点（斯坦纳顶点可覆盖也可不覆    盖），这样一棵树就叫做斯坦纳树。最小斯坦纳树也是一个NP-hard问题。

    （网图，将就着看......）

     

    如上图所示，{1，3，4，5}为节点集合R，现在全集中找出节点集合C使其包含节点集合R且权值和最小。结果为选择{1，2，3，4，5，6}，权值和为11。

11. 边界框

    边界框是指包含线网所有顶点的一个最小砖。如下图所示。

     

    

    其周长为：

     

12. 单树干斯坦纳树

         单树干斯坦纳树也是一种斯坦纳树，它先确定树干的位置，然后所有顶点向树干    作垂直线或者水平线。线网长度以上述两棵树的平均值表示。

     

     

    

    如上图所示，方块即为树干，它的坐标是所有顶点坐标的平均值。

    即为线长估计值。

    总结

    最小斯坦纳树的计算精度最高，但计算量也最大，因其也是一个NP-hard问题。边界框法计算量很小，但是由此带来的误差也最大（指与最短路径长度相比）。单树干斯坦纳树综合考虑了精度与计算量，很多布局算法用它作为最终布局结果的总线长估计。

     

    初始布局

    对于启发式算法，一个良好的初始布局能减少迭代次数，大大减少计算量。初始布局算法又可以分为选择算法和安置算法两部分。选择算法负责从未被安置的模块中选择一个或一组作为下一步需要安置的对象，而具体怎样安置则交由安置算法进行处理。

    需要注意的是，选择算法与安置算法应有相同的目标函数。

    选择算法

    根据目标函数的不同，选择算法又可以分为连线总长最小、单元张力总和最小、割值函数最小等几种。

     

     

    安置算法

    （哎呦我去可算写到正式布局了……）

    本章名词解释：

    Pad:引出节点，可以理解为硅片的管脚，封装在芯片内部。

    Pin:芯片封装好后的管脚，显露于外（如果做过电路实验应当对pin印象深刻）。

        将一个模块放置在芯片上时，我们会希望安置完成后连线总长度最小，使连线总长度最小的位置被称为"重心"。

    安置策略决定初始模块的位置，又可分为核心生长法和边生长法两种。顾名思义，核心生长法将选定的模块安置在芯片中心，随着后续模块的安置，整体向四周扩展。其缺陷在于，若对pad的位置有要求，那么由于核心生长法在最后才覆盖至芯片边缘，pad的位置和顺寻就无法作出更改，因其取决于先前模块的安置结果。由此引出边生长法。

    边生长法将pad作为构造的初始单元，随着安置工作的进行，由芯片的边缘向中心扩展。此法有利于提高布线均匀度，适宜多元胞模式和门阵列模式的初始布局。

    安置算法根据布局模式的不同，又可以分为一维安置和二维安置两种。例如标准单元或门阵列行内单元的安置属于一维安置。

    1. 一维安置算法

       等分接点和重心法常用于求解一维安置。它们的区别在于其他已经被安置好的模块与需要被安置的模块之间被赋予的权重是否相同。若相同则使用等分接点法，否则使用重心法。

       等分接点法的本质就是简单地求各模块的平均值，得到的平均值即为被安置的模块理应被放置的位置。

       而重心法：

       其中，X为重心x轴坐标，x_i为第i个模块的x坐标，v_i为第i个模块的权重值，假设共有n个模块。重心y轴坐标Y与之类似。等分接法也可理解为权重全为1时的重心法。

        

    2. 二维安置算法

     

    若用边界框估计第i个线网，边界框左下角坐标为（,)，右上角坐标为(,)，假设待安置的模块坐标为(x,y)，有总连线长度：

    其中

    与之类似。

     

    迭代布局

    迭代布局的目的是为了达到目标函数尽可能最优，对模块路线进行调整。常用启发式函数，如模拟退火算法，蚁群算法等。这里我们介绍A-star算法，它也是一种启发式算法。

13. star算法

    A-star算法与Dijkstra算法相似，不同之处在于A-star算法计算优先级方式如下：

    其中f(n)为节点的综合优先级，选择下一个节点时总选择综合优先级最高（也就是f(n)最小的节点），g(n)为节点距起点的带权路径长度，而h(n)是节点n距离终点的预计代价，h(n)如何计算会在之后解释。

    当f(n)>>h(n)时，成为Dijkstra算法。

    当f(n)<<h(n)时，成为最佳优先搜索算法。

     

    A-star算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。

    另外，A-star算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为open_set和close_set。

    返回

    启发函数

    我们先详细说明h(n)，h(n)可以理解为A-star算法的启发函数(在本文档之《布局布线算法详细介绍》中对此有介绍）。

    定义节点n到终点的精确代价为X。以下讨论的均为全过程成立的情况。

    h(n)=0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。

    h(n)<X，则A-star算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。

    h(n)=X，则A-star算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。

    h(n)>X，则A-star算法不能保证找到最短路径，不过此时会很快。

    在另外一个极端情况下，如果h(n)相较于g(n)大很多，则此时只有h(n)产生效果，这也就变成了最佳优先搜索。

    由上面这些信息我们可以知道，通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可。这也是A-star算法比较灵活的地方。

    对于网格形式的图，有以下这些启发函数可以使用：

    如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离。

    计算曼哈顿距离的函数如下，这里的D是指两个相邻节点之间的距离因子，通常是一个固定的常数。

    function heuristic(node) =
    

        dx = abs(node.x - goal.x)
    

        dy = abs(node.y - goal.y)
    

        return D * (dx + dy)
    						

     

    如果图形中允许朝八个方向移动，则可以使用对角距离。D2指的是两个斜着相邻节点之间的距离因子。若所有节点均为正方形，其值为

     

    function heuristic(node) =
    

        dx = abs(node.x - goal.x)
    

        dy = abs(node.y - goal.y)
    

        return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
    

     

    如果图形中允许朝任何方向移动，则可以使用欧几里得距离。欧几里得距离是指两个节点之间的直线距离。欧几里得距离在生活中经常用到。

    function heuristic(node) =
    

        dx = abs(node.x - goal.x)
    

        dy = abs(node.y - goal.y)
    

        return D * sqrt(dx * dx + dy * dy)
    

     

    算法流程

     

    * 初始化open_set和close_set；
    							

    * 将起点加入open_set中，并设置优先级为0（优先级最高）；
    							

    * 如果open_set不为空，则从open_set中选取优先级最高的节点n：
    							

        * 如果节点n为终点，则：
    							

            * 从终点开始逐步追踪parent节点，一直达到起点；
    							

            * 返回找到的结果路径，算法结束；
    							

        * 如果节点n不是终点，则：
    							

            * 将节点n从open_set中删除，并加入close_set中；
    							

            * 遍历节点n所有的邻近节点：
    							

                * 如果邻近节点m在close_set中，则：
    							

                    * 跳过，选取下一个邻近节点
    							

                * 如果邻近节点m也不在open_set中，则：
    							

                    * 设置节点m的parent为节点n
    

                    * 计算节点m的优先级
    							

                    * 将节点m加入open_set中
    							

     

     

    图解

     

    下面通过图解的方式解释A-star 算法的工作流程。

    

    如图所示，绿色点为start设为A，红色点为goal设为B，蓝色点为不可通过的障碍物，黑色点为自由区域。目标是规划从A到B的路径。

    开始

14. 从A点开始，首先将A点加入开启列表，此时取开启列表中的最小值，初始阶段开启列表中只有A一个节点，因此将A点从开启列表中取出，将A点加入关闭列表。

     

     

15. 取出A点的相邻点，将相邻点加入开启列表。如图所示，此时A点即为相邻点的父节点。图中箭头指向父节点。将相邻点与A点加入追溯表中。

    

    计算评分

    对相邻点，一次计算每一点的g，h，最后得到f = g + h。如图，节点的右下角为g值，左下角为h值，右上角为f。

    

     

    选最小值，再次搜索

    选出开启列表中的F值最小的节点，将此节点设为当前节点，移出开启列表，同时加入关闭列表。如图所示。

    取出当前点的相邻点，当相邻点为关闭点或者墙时，不操作。此外，查看相邻点是否在开启列表中，如不在开启列表中将相邻点加入开启列表。如相邻点已经在开启列表中，则需要进行G值判定

    

    G值判定

    对于相邻点在开启列表中的，计算相邻点的G值，计算按照当前路径的G值与原开启列表中的G值大小。如果当前路径G值小于原开启列表G值，则相邻点以当前点为父节点，将相邻点与当前点加入追溯表中。同时更新此相邻点的H值。如果当前路径G值大于等于原开启列表G值，则相邻点按照原开启列表中的节点关系，H值不变。因为图示中，当前点G值比原开启列表G值大，因此节点关系按照原父子关系和F值。

    计算耗费评分，选最小值

    此时计算开启列表中F值最小的点，将此节点设为当前节点，并列最小F值的按添加开启列表顺序，以最新添加为佳。

    

    重复搜索判定工作

    直到当goal点B加入开启列表中，则搜索完成。此时事实上生成的路径并一定是最佳路径，而是最快计算出的路径。若判定标准改为当goal点B加入关闭列表中搜索完成，则得出路径是最佳路径，但此时计算量较前者大。

    当没有找到goal点，同时开启列表已空，则搜索不到路径。结束搜索。

    

     

    生产路径

    由goal点B向上逐级追溯父节点，追溯至起点A，此时各节点组成的路径即使A*算法生成的最优路径。

     

    Dijkstra算法

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

    算法思路

    1. 指定一个节点，例如我们要计算 ‘A‘ 到其他节点的最短路径
    2. 引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意 如上图所示，A->C由于没有直接相连 初始时为∞）
    3. 初始化两个集合，S集合初始时 只有当前要计算的节点，A->A = 0，
       U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞
    4. 从U集合中找出路径最短的点，加入S集合，例如 A->D = 2
    5. 更新U集合路径，if ( ‘D 到 B,C,E 的距离‘ + ‘AD 距离‘ < ‘A 到 B,C,E 的距离‘ ) 则更新U
    6. 循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径。

    算法图解

    1.选定A节点并初始化，如上述步骤3所示

    

    2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( ‘D 到 B,C,E 的距离‘ + ‘AD 距离‘ < ‘A 到 B,C,E 的距离‘ ) 来更新U集合

    

    3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( ‘B 到 C,E 的距离‘ + ‘AB 距离‘ < ‘A 到 C,E 的距离‘ ) ，如图所示这时候A->B距离 其实为 A->D->B

    

    4.继续

    

    5.结束。

    

     

    返回

布局布线算法（公式后补）

原文：https://www.cnblogs.com/BYGAO/p/14628094.html