图论小论文.doc

Dijkstra算法在移动通信中的应用 李鹏翔 信息与通信工程学院 1、问题的提出 在移动通信中，尤其是端到端的通信中，常常会涉及到最短路问题。但是，这里的最短路不仅仅指一般地理意义上的距离最短由于基站与基站之间、基站与终端之间的距离、阴影等因素我们将这些因素归一化，赋予它们以不同的权值，权值越小说明信道状况越好。端到端之间最短路问题实际上是寻找所有可能路径之中权值最小的路径。一个实际问题如下： 上图中，我们假设与为两个移动用户，为四个基站基站与基站间、基站与终端间的权值，求从到应选择哪一路径使权值最小。 2、算法简介 Dijkstra算法是图论中确定最短路的基本方法也是其它算法的基础Dijkstra算法基本步骤： 令： 并令： （1）、对，求。 （2）、求得，使= 令 （3）、若则已找到到的最短路距离否则令从中删去转（1）。 这样经过有限次迭代则可以求出到的最短路线可以用一个流程图来表示： 第一步：先取意即到的距离为0而是对所赋的初值。 第二步：利用已知根据对进行修正。 第三步：对所有修正后的求出其最小者其对应的点是所能一步到达的点中最近的一个由于所有因此任何从其它点中转而到达的通路上的距离都大于直接到的距离因此就是到的最短距离所以在算法中令并从s中删去若k=n则就是到的最短路线计算结束。否则令回到第二步继续运算直到k=n为止。 这样每一次迭代得到到一点的最短距离重复上述过程直到。 3、问题的解决 下面我们用Dijkstra算法解决我们遇到端到端通信的最短路问题。 为了方便计算先作出该通信网的权值矩阵如下 （0）、设 （1）、第一次迭代 ①计算如下 ； ； ； ； ②取,令 ③由于,令转(1) （2）、第二次迭代 ①算如下 ; ; ; ; ②取令 ③由于,令转(1) （3）、第三次迭代 ①算如下 ； ； ； ②取 ③由于,令转(1) （4）、第四次迭代 ①算如下 ； ； ②取 ③由于,令转(1) （5）、第五次迭代 ①算如下 ； ②由于。因此已找到到的最短距离为12。计算结束。 找最短路线逆向追踪得 最短距离为12即从城市到城市的距离最短,即费用最省。 4、结语