 |
Ganushchak Nadia
|
Abstract |
In our time Geographic Information Systems (GIS) are getting more and more popular in many application areas. One of GIS-technology application is network analysis, where the key problem is the commutation of shortest path between different locations on a network. The shortest path problem is always actual for ambulance service, urgency teams, police, ets. A problem of choosing the optimal route arises before everybody when it is necessary to go somewhere. So, an aim of thins work is to decide, which shortest path algorithm run as fast as possible and optimality on real road networks. The problems of this work are realization of three shortest path algorithms in GIS-application, testing of three algorithms on real transport networks with different limits and conditions, doing evaluations of execution time and accuracy of algorithms with different conditions, ets. The former researches similar to this work tested and analyzed other algorithms. That is why in this work researching and evaluating of best shortest path algorithm between Dijkstra’s algorithm, Worshell-Flojd’s algorithm and Lewitt’s algorithm are be done. It can be more effective and it can run faster if results of evaluations can be used in software development. Results of this researching will be important for software programmers and users of this software (medicine, police, transport organizations, ets.). Some studies on the performance of the shortest path algorithms have been done so far. For example, in article [1] processing time of Dijkstra’s Algorithm, Huristic Methods and Genetic Algorithm using the Visual Basic, Visual C++ and Mapobject programming languages was evaluated. The set of one-to-one, one-to-all and all-to-all shortest paths was found. The number of nodes in network was different: from 500 to 5000. The final results of evaluation were:
In article [2] Dijkstra’s, Yen’a and Floyd’s algorithms were described and realized. These shortest path algorithms were realized in database management system FoxPro 6.0. in this article it is said apriory that Dijkstra’s algorithm performers better for one-to-one shortest path, Floyd’s algorithm performers better for the shortest pats between all pair of nodes in network, Yen’s algorithm performers better for set of the one-to-one shortest paths. So in article [2] the shortest path algorithms are not compared with each other, there are just analyzed separately. In article [3] tree algorithms were studied and realized in Borland Delphi 6 application. But there is not clear answer which algorithm was better for task given. So nobody can say definitely, which shortest path algorithm is optimal for network analysis problem decision in GIS application. Besides, there is not clear answer how to compare real geographic address of object (number of house, name of street, town, region, ets.) with node in network exactly, fast and with minimal expenditures. It is not clear how to comply address’s text which user has entered to link it with corresponded node in GIS-application network. Next problem didn’t have clear answer too. We need a program, which must have minimal size (occupies minimal place on hard disk of PC), use minimum of resources of PC and be maximum effective. We need to know, which programming language we must use to meet this demand to realize shortest path algorithms. We can see that there are many undecided problems in network analysis and in network analysis in GIS-application particularly. A little illustration of my work is on Figure 1:  Figure 1 - Shortest path from A to B The result of my researching work is considering the Dijkstra’s, Worshell-Flojd’s and Lewitt’s algorithms. These algorithms were realized in Borland Delphi 5 application, analyzed and compared in ArcView GIS 3.1 on real transport network (Voroshilov region of Donetsk) in scale 1:10000. the results of my work are:
In future I’m planning to test these algorithms on 1000-nodes real transport network and do comparison of the algorithms with different conditions. After these studies it’s clear that shortest path problem is still actual in many application areas. But there are not many researches which have found best shortest path algorithm in different conditions. If we use results of all these researches in software development, programs will be more effective and productive. Refrences
|
: