A Method of Finding the Shortest Path Between Nodes in Networks Based on Thermal Flux Spreading

摘要

In this paper, we propose a physical method of thermal conduction for searching the shortest path between two nodes in complex networks. In this method, a thermal flux matrix of nodes is constructed, and in which the element with the maximal value in each node thermal flux vector indicates one section of the shortest path form the nodes to the source node. The method allows for finding the correct shortest . path form source node to any other nodes simultaneously. Theoretical analysis and experimental results show that the method has high accuracy and low computation complexity. The shortest path from the source node to any other nodes can be found in time O(mt/△t), where m is the number of edges, t is the conduction time, At is the integral interval, which is essentially in linear time with m, and all the shortest path between any two nodes can be found in time O(nmt/2△t).