Font Size: a A A

The Shortest Path Algorithm Research Of Application In Multicasting Routing And Physical Distribution

Posted on:2008-04-05Degree:MasterType:Thesis
Country:ChinaCandidate:J G MaFull Text:PDF
GTID:2120360212974817Subject:Information Science
Abstract/Summary:PDF Full Text Request
The Shortest Path Algorithm is widely used in various applications, especially Dijkstra is used in different areas as the key algorithm for Shortest Path Algorithm. In the thesis the improved Dijkstra algorithms are separately used in multicasting routing with delay constraint and physical distribution path optimization.Some basic concepts of Graphics are introduced in the thesis which are the foundation of Short Path research. The multicasting Routing is also introduced in the thesis and an improved Dijkstra algorithm is introduced and used in Multicasting Routing. There are some similarities between geography networks and Graphics and we compare transportation path to arcs in Graphics and transportation spots to vertexes in Graphics. We use Dijkstra algorithm to optimize Vehicle Routing.We explain the concept of multicast routing under delay and delay variation constraints, and then present a multicast routing algorithm LCDVMR to find a routing tree with delay and delay variation constraints. This algorithm is based on extended Dijkstra shortest path algorithm, and has a low complexity which is near to the complexity of Dijkstra shortest path algorithm. Experiment results show that comparing to DVMA, the succeed rate to solve this problem is 7% higher than that generated by DVMA.We choose heap sort to improve the efficiency of Dijkstra Algorithm. The solutions to optimize transportation path are introduced in the thesis and the solutions are all based on improved algorithms. Finally we use a modified way to deal with more complicated conditions.
Keywords/Search Tags:The shortest path, Dijkstra algorithm, Multicasting routing, Vehicle routing, Delay constraint
PDF Full Text Request
Related items