Title: Improvement and Simulation of Dijkstra Algorithm Based on Backtracking Algorithm
Abstract: In view of all of the shortest path problem,this paper put forward an improveed Dijkstra algorithm based on the weighted graph adjacency matrix. First of all,the shortest path length vector was obtained from a vertex to all other vertices. Then it structsed an identity matrix by adjacency matrix and shortest path length vector. Finally,it used the backtracking algorithm and the identity matrix to search out all shortest paths obtained from the starting point to all other vertices. This algorithm has the advantages of wide using range,small scale of calculation,simplified calculation process,and easy realizaion with a computer. The core of the algorithm is to use backtracking to solve all the shortest path computation. The paer put forward a backtracking method to solve the problem from the end to the starting point,discussed and gave a fast algorithm for any two vertices to find all the shortest path. The algorithm makes full use of the path information obtained from the identity matrix to search all shortest paths between the two vertices by backtracking. The simulation results show that it is very effective to find all of the shortest paths between any two vertices.
Publication Year: 2013
Publication Date: 2013-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot