[科普中国]-最短路由选择算法

在静态路由选择算法中，最短路由选择(Shotest Routing) 算法是一种简单易懂而应用广泛的技术。它的基本思想是：建立一个子网图，图中每一个节点代表一台路由器，每条弧线代表一条通信线路（链路），弧上的数字代表该线路的权重。为了在一对给定的路由器之间选择一条路由路径，路由算法只需在图中找到这对节点之间的最短路径即可。对于路径长度测量有多种方法，一种方法是计算站点数量，另外也可以计算距离、信道带宽、平均通信量、通信开销、队列长度、传播时延等。

计算图中两个节点之间的最短距离有多种算法，其中最著名的算法是Dijkstra在1959年提出的Dijkstra算法1。该算法要求每个节点用从源节点沿已知最佳路径到本节点的距离来标注。开始时由于一条路径也不知道，故所有的节点都标注无穷大。随着算法的进行和不断找到的路径，标注随之改变，使之反映出较好的路径。一个标注可以是暂时性的(可更改的)，所有标注最初都是暂时的，但一旦发现了标注代表了从源节点到该节点的最短可能路径时，就使之成为永久性的，不再进行修改。

为了说明加标注算法是怎样工作的，请参考右图，其中数字表示两节点的距离。要找A至D的最短距离，首先A标注为永久性的(用实心圆点表示)作为开始，然后依次考察与A相邻的每个节点，用他们各自到A的距离重新标注这些点。找到B节点为最短路径节点后使其成为永久节点，接下来从节点B开始，检查所有与B相邻的节点，如果B的标注与从B到所有节点距离之和小于此节点的标注，就重新标注这个节点。2

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学