Fast Algorithms To Find The Shortest Path Using Matrices
[Full Text]
AUTHOR(S)
Wafaa Mustafa Hameed, Asan Baker Kanbar, Jumah Aswad Zarnan
KEYWORDS
shortest path, matrix, nods, arcs, network, algorithms, optimization
ABSTRACT
Shortest path algorithms are among the most studied network flow optimization problems introduced to in such approach such as ants colony, Greedy, Floyd, K and k* algorithms. In this paper we introduce a new algorithm to find the shortest path between two centers (nods), these nods may be represent a fire zone, bus station, cities…etc.In this algorithm nods will be represents as a matrix, the number of columns and Rows equal to the number of arcs of the network. The elements represent as 0 that means that there’s no arc between the centers (nods), or 1 that’s mean there’s an arc between the two centers. The solving of this matrix occurs in many stages: Stage1: specifying the number of arcs in the network by calculating the number of elements equal to 1 as arrow of matrix. Stage2: specify the number of arcs by identifying the number of rows and columns hold the value 1. Stage3: count the length of the paths depending on the arcs which is installation the paths and compare between these paths to specify the shortest path. So in this algorithm we need just to inter the number of arcs, start state node and goal state node of the network, we choose VC++ as a language to program this application in, a compiled program will always be faster than an interpreted program.
REFERENCES
[1] Fasial Khamayseh,Nabil Arman,”Improvement of ShortestPath Algorithms Using Subgraphs Heuristics”,JATIT,vol.76.NO.1,JUN.2015.
[2] T.H.Cormen,C.E.Leiserson, R.L.Rivest,and C.Stein.”Dijkstras’s Algorithm.Introduction to Algorithms (second ed.).Section 24.3:pp.595601.MIT Press and MC Graw Hill.2001.ISN 0262032937.
[3] N.Arman, “An Efficient Algorithm for Checking Path Existence Between Graph Vertices”, Proceeding of the 6th international Arab Conference on Information Technology (ACIT, 2005), pp.471476, December 68.2005, AlIsra Private University, Amman,Jurdan,2005.
[4] David Eppstein “Finding the K Shortest Path”, University of California ,http://www.Ics.uci.edu/eppsteien/. March 31, 1997.
[5] Husain Ajazzar, Stefan Leue,”K*: A heuristic Search Algorithm for Finding the K Shortest Paths”. Artificial Intelligence, 174 (2011)2122154.
[6] Ahmad Younes Hmed ,”A Genetic algorithms for finding the K Shortest path’s in a Network”, Egypt Informatics Journal (2010) 11,7579.
[7] A.W.Brander and M.C.Sinclair, “A Comparative Study of K Shortest Path Algorithms”. Proc.11th UK performance Engineering Worsh. For computer and Telecommunications Systems, September, 1995.
[8] R.K.Ahuja,K.Mehlhorn,J.B.Orline, and R.E.Tarjan,”Faster Algorithms for the Shortest Path Problem”,J.Assoc compute.Mach.37:213223.Assoc.forcomputing Machinary,1990.
[9] T.H.Byers and M.S.Waterman,”Determining all Optimal and NearOptimal Solutions When Solving Shortest Path Problems by Dynamic Programming”. Operations Research 32:13811384,1984.
[10] Marius Glabowski, Bartoz Musznicki, Przemyslaw Nowrk, “Shortest Path Problem Solving Based on Ant colony Optimization Meta heuristic”, image Processing &Communication, Vol.17,no.12,PP.718. DOI:10.2478/V1024801200115
[11] P.N.Klen, S.Rao, M.H.Rauch, and S.Subramnian.”Faster Shortestpath Algorithms for Planner Graph”.Proc.26th Symp. Theory of Computing.PP.2737.Assoc.for Computing Machinary, 1994.
