在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman-Ford算法和Dijkstra算法。这两种算法的思路不同，但得出的结果是相同的。在下面只介绍Dijkstra算法，它的已知条件是整个网络拓扑和各链路的长度。
应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。
下面以图F-1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便起见，设源结点为结点1。然后一步一步地寻找，每次找一个结点到源结点的最短路径，直到把所有的点都找到为止。
令D（v）为源结点（记为结点1）到某个结点v的距离，它就是从结点1沿某一路径到结点v的所有链路的长度之和。再令l（i，j）为结点i至结点j之间的距离。整个算法过程如下：
1）初始化。令N表示网络结点的集合。先令N={1}。对所有不在N中的结点v，写出
在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子，可以使D（v）=99。
图F-1 求最短路径算法的网络举例
2）寻找一个不在N中的结点w，其D（w）值为最小。把w加入到N中。然后对所有不在N中的结点v，用[D（v），D（w）+l（w，v）]中的较小的值去更新原有的D（v）值，即
D（v）←Min[D（v），D（w）+l（w，v）]
3）重复步骤2），直到所有的网络结点都在N中为止。
表F-1是对图F-1的网络进行求解的详细步骤。可以看出，上述的步骤2）共执行了5次。表中带圆圈的数字是在每一次执行步骤2）时所寻找的具有最小值的D（w）值。当第5次执行步骤2）并得出了结果后，所有网络结点都已包含在N之中，整个算法即告结束。
表F-1 计算图F-1的网络的最短路径
现在对以上的最短路径树的找出过程进行一些解释。(www.xing528.com)
因为选择了结点1为源结点，因此一开始在集合N中只有结点1。结点1只和结点2，3和4直接相连，因此在初始化时，在D（2），D（3）和D（4）下面就填入结点1到这些结点相应的距离，而在D（5）和D（6）下面填入∞。
下面执行步骤1）。在结点1以外的结点中，找出一个距结点1最近的结点w，这应当是w=4，因为在D（2），D（3）和D（4）中，D（4）=1，它的之值最小。于是将结点4加入到结点集合N中。这时，在步骤1）这一行和D（4）这一列下面写入①，数字1表示结点4到结点1的距离，数字1的圆圈表示结点4在这个步骤加入到结点集合N中了。
接着就要对所有不在集合N中的结点（即结点2，3，5和6）逐个执行（F-1）式。
对于结点2，原来的D（2）=2。现在D（w）+l（w，v）=D（4）+l（4，2）=1+2=3>D（2）。因此结点2到结点1距离不变，仍为2。
对于结点3，原来的D（3）=5。现在D（w）+l（w，v）=D（4）+l（4，3）=1+3=4<D（3）。因此结点3到结点1的距离要更新，从5减小到4。
对于结点5，原来的D（5）=∞。现在D（w）+l（w，v）=D（4）+l（4，5）=1+1=2<D（5）。因此结点5到结点1的距离要更新，从∞减小到2。
对于结点6，现在到结点1的距离仍为∞。
步骤1）的计算到此就结束了。
下面执行步骤2）。在结点1和4以外的结点中，找出一个距结点1最近的结点w。现在有两个结点（结点2和5）到结点1的距离一样，都是2。选择结点5（当然也可以选择结点2，最后得出的结果还是一样的）。以后的详细步骤这里就省略了，读者可以自行完成剩下的步骤。
图F-2 用Dijkstra算法求出最短路径树的各个步骤和在结点1的路由表
最后就得出以结点1为根的最短路径树。图F-2给出了各步骤执行后的结果。从最短路径树可清楚地找出从源结点（结点1）到网内任何一结点的最短路径。图F-2还给出了在结点1的路由表。此路由表指出对于发往某个目的结点的分组，从结点1发出后的下一跳结点（在算法中常称为“后继结点”）和距离。当然，像这样的路由表，在所有其他各结点中都有一个。但这就需要分别以这些结点为源结点，重新执行算法，然后才能找出以这个结点为根的最短路径树和相应的路由表。
[1]注：对channel的标准译名是“信道”，又称“通路”。本书选用了后者。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
