关键词: 动态网络, 最短程, 先进先出, 弱FIFO

Abstract: We analyze the research status of finding the shortest path of dynamic networks, analyze the complexity of getting the shortest path, study the relationship between the structure of the dynamic networks and finding the shortest path of the dynamic networks. It is proved that dynamic networks defined by velocity automatically meet weak FIFO’s condition. The networks whose passing function of any side is not decreasing function equals dynamic networks which use velocity. The sufficient condition of directly using Dijkstra algorithm to get the shortest path is that the networks must meet weak FIFO’s condition. How to build a dynamic network which can automatically meet FIFO’s condition or meet FIFO’s equivalent condition is studied, and an algorithm of getting the shortest path of the dynamic networks is given. An example is given to explain the validity of our methods.

Key words: dynamic networks, the shortest path, first in first out, weak FIFO