交互网络上任意节点对的最短路径集解法

交互网络上任意节点对的最短路径集解法

吴向君;任凯

【期刊名称】《海军工程大学学报》

【年(卷),期】2011(023)004

【摘要】The search for the shortest paths is an important part of studying the structure of interac tive networks. By using common algorithms of Dijkstr and Floyd, only one path can be got in the search process. But in fact, there are more than one shortest paths between nodes in the interactive networks. Thus, the shortest paths in the weighted interaction network were calculated with the Floyd Algorithm. By inserting all the other nodes of the interaction network into each pair of nodes with the shortest path, the distance between the nodes can be calculated. Compared with the distance calculated by the Floyd algorithm, all the middle nodes on the shortest path were sorted out to con struct the paths olding tree and establish the shortest path set with any nodes. This method is useful for searching all the shortest paths.%搜索交互网络中的最短路径是研究网络结构的重要内容,在常见的Dijkstr和Floyd算法中,只能获取一条最短路径.在交互网络上任意节点对之间的最短路径不止一条的情况下,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,在其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的路径,通过与Floyd算法后的最短路径进行比较,筛选出构成最短路径的所有中间节点,构建路径支撑树.基于路径支撑树确定任意节点对