| Network optimization problem is a kind of classical optimization problem in graph theory,including the shortest path problem,the maximum capacity path problem,the fastest path problem and so on.It has an important use in production and life.For traditional network optimization problems,most researches are based on static networks.In actual situations,the state of the network changes over time.We call this type of network a time-varying network.Therefore,compared with the static network,the time-varying network can better describe the dynamic state of the network,which is more in line with the situation in production and life.This paper studies the optimal path algorithm in time-varying networks,which is mainly divided into three parts:First,Research on the shortest path model of time-varying networks based on priority queues.Firstly,the shortest path problem of time-varying networks is defined,and a shortest path algorithm for time-varying networks based on priority queue is proposed.Theorems and experiments prove that the proposed algorithm can find the global optimal solution.Second,Research on the maximum capacity path model of time-varying networks based on priority queues.After the problem of the maximum capacity path of the timevarying network is defined,the shortest path model of the time-varying network based on the priority queue is improved and adjusted.First,the node state is defined;second,the iterative process of the priority queue is adjusted,and finally the path generation algorithm is adjusted.Experiments show that the proposed algorithm can obtain the global optimal solution compared with the classic algorithm.Third,Research on the fastest path model of time-varying networks based on priority queues.The fastest path problem of time-varying network is defined,and the fastest algorithm of time-varying network based on priority queue is proposed.The optimal edge curve is defined,and the trend of transmission cost in different situations is analyzed. |
PDF Full Text Request