一种求网络最短路径的商空间覆盖模型及其构建方法

摘要

本发明公开了一种无向无权网络的商空间覆盖模型及其构建方法，特征是利用商空间理论和相容关系对网络求极大完全子图，逐步粒度粗化形成一递阶商空间覆盖网络链，得到粒度由细到粗的各级商空间覆盖网络所有极大完全子图及其在初始网络中的节点信息而形成的商空间覆盖模型；根据该商空间覆盖模型中各级商空间覆盖网络的极大完全子图在初始网络中的节点信息，可直观找出网络的两节点间的最短路径长度，根据模型可以找到初始网络两节点在不同粒度商空间覆盖网络的位置，从粒度粗的商空间覆盖网络开始搜索两点间的连通路径，逐步细化，一直到搜索到粒度最细的商空间，从而可快速搜索出任意两点的最短路径；还可利用计算机来构建商空间覆盖模型。

主权项

1、一种商空间覆盖模型的构建方法，根据无向无权网络中网络拓扑结构的网络中极大完全子图，对节点粒度分类建立层次网络模型；其特征在于：对于无向无权连通网络从作为粒度最细、第0级商空间覆盖网络的初始网络开始，搜索网络中所有的极大完全子图，以极大完全子图为节点，两极大完全子图的节点间有公共节点或边，定义两节点相连，得到粒度较粗的商空间覆盖，为初始网络的一级商空间覆盖网络；然后再求初始网络的一级商空间覆盖网络的所有极大完全子图，并记录极大完全子图对应于初始网络中的节点信息，以该级的极大完全子图为节点，两极大完全子图的节点间有公共节点或边，定义两节点相连，得到粒度较粗的商空间覆盖，构成初始网络的二级商空间覆盖网络，求初始网络的二级商空间覆盖网络的所有极大完全子图，并记录该级的极大完全子图对应于初始网络中的节点信息；继续依此操作直至在商空间覆盖网络的极大完全子图对应于初始网络的节点信息中初始网络的任意两节点对都在同一个极大完全子图中；各商空间覆盖网络按构成先后顺序排列形成一个递阶商空间覆盖网络链；按递阶商空间覆盖网络链的顺序，记录各个商空间覆盖网络的所有极大完全子图和各个极大完全子图对应于初始网络的节点信息为商空间覆盖模型；对于无向无权的不连通网络，先求出各个连通分支，对于每个连通分支，用无向无权连通网络的方式来求解连通分支的商空间覆盖模型。