一种带约束条件的拓扑图最优路径算法

摘要

本发明公开了一种带约束条件的拓扑图最优路径算法，包括将电信设备生成拓扑节点、光纤连接生成拓扑链路，组成拓扑矩阵；选择源、宿拓扑节点；按约束条件建立必经拓扑节点和拓扑链路列表，并将必经拓扑链路转化为必经拓扑节点加到必经拓扑节点列表中；按约束条件建立避开拓扑节点和拓扑链路列表，并更新拓扑矩阵；设置当前寻路的起始和终结拓扑节点为Nt和Ne；当Nt连接拓扑链路L<t，e>，将Nt、Ne和L<t，e>加入整体路径，否则寻找Nt、Ne间最优路径加入整体路径中；如果Ne为宿拓扑节点则结束，否则据Nt、Ne间最优路径更新拓扑矩阵，开始下一次迭代。本发明实现了在约束条件下寻找最优路径，并通过改进Dijkstra算法，提高在源拓扑节点度数大时的寻路效率。

主权项

一种带约束条件的拓扑图最优路径算法，其特征在于，包括以下步骤：步骤S10、将电信传输网中所有电信设备抽象生成拓扑节点，电信设备间的所有光纤连接抽象生成拓扑链路，组成拓扑矩阵；步骤S20、选择源拓扑节点Ns和宿拓扑节点Nd；步骤S30、选择路径必须经过的拓扑节点和拓扑链路，按预设顺序建立必经拓扑节点列表和必经拓扑链路列表，并将必经拓扑链路转化为必经拓扑节点，顺序添加到必经拓扑节点列表中；步骤S40、建立避开拓扑节点列表和避开拓扑链路列表，并更新拓扑矩阵；步骤S50、设置当前寻路的起始拓扑节点和终结拓扑节点分别为必经拓扑节点Nt和Ne，并判定必经拓扑节点Nt是否连接必经拓扑链路L<t，e>，如果是，执行步骤S60；否则，执行步骤S70；步骤S60、将必经拓扑节点Nt、Ne和必经链路L<t，e>加入到整体路径中，执行步骤S80；步骤S70、在必经拓扑节点Nt、Ne间寻找最优路径，加入到整体路径中，执行步骤S80；步骤S80、判断当前终结拓扑节点Ne是否为宿拓扑节点Nd，如果是，则结束程序；否则，执行步骤S90；步骤S90、将必经拓扑节点Nt、Ne间最优路径中的拓扑节点设置为避开的拓扑节点，将必经拓扑节点Nt、Ne间的最优路径中的拓扑链路设置为避开的拓扑链路，然后执行步骤S40。