Research Of The Shortest Path Tree On Uncertain Graph

In communication networks,multicast is an important means of communication,it is a one-to-many type of communication.With the development of net work technology,the multicast is widely used in the distributed system,video,etc.The key to the implementation of the multicast is to select the rational multicast algorithm to construct a multicast tree.We use a weighted undirected graph to represent the communication network,the weights of graph edges indicate the consumption of communication between two nodes,the multicast tree is actually the shortest path tree in weighted undirected graph.In communication networks,however,for some reason can lead to physical link between nodes disconnect or loss of data,we not only need to select a new multicast tree to ensure that the source point to the link between each node flow and data integrity,but also to ensure that the entire communication cost minimum,thus the research of the shortest path tree in uncertain graph is of great significance.This paper mainly discusses the shortest path tree algorithm in the uncertain graph,and obtains the following progress:(1)Because there is uncertainty in the edges of the uncertain graph,so in the study the shortest path tree problem in uncertain graph can no longer use the method in determine graph,we put forward the concept of the shortest path tree on uncertain graph,and present the concept of optimal shortest path tree.The optimal shortest path free refers to the shortest path tree of the smallest weighs.We design the optimal shortest path tree algorithm in the uncertain graph with the thought of edge transformation,the algorithm mainly through continuous change into the weights of the small side for sharing path,thereby lowering the value of the shortest path tree,finally the optimal shortest path tree is obtained,and then by reducing the judgment number of edge transformation can effectively improve the operation efficiency of the algorithm.(2)The reliability of the shortest path tree in the uncertain graph is analyzed.The reliability of all reliable implicated graphs is the reliability of the shortest path tree,we put forward a new calculation method to calculate the reliability of the shortest path tree,on this basis,and present the concept of the most reliable shortest path tree.The most reliable shortest path tree is the shortest path tree with the highest reliability in uncertain graph.We design the most reliable shortest path tree algorithm in the uncertain graph with the thought of edge transformation.The algorithm mainly through continuous change into a high probability of being side to improve the reliability of the shortest path tree,and the most reliable shortest path tree is obtained,then by reducing the judgment number of edge transformation can effectively improve the operation efficiency of the algorithm.Finally,through the analysis of examples and related experiment,the feasibility of the optimal shortest path tree algorithm and the most reliable shortest path tree algorithm is proved,we get the solution to the problem correctly.