In the paper we discuss and compare two commonly used methods of finding the shortest paths in networks,namely Dijkstra’s and A*algorithms.We compare their effectiveness in terms of traversing road network in circums...In the paper we discuss and compare two commonly used methods of finding the shortest paths in networks,namely Dijkstra’s and A*algorithms.We compare their effectiveness in terms of traversing road network in circumstances that require swift decision making in the event of dynamically changing road conditions on the basis of studies conducted for evacuation plans.To build a proper model of such a network,a method of appropriate edge-weighting is introduced,based on empirical data collected by other researchers.Then,we use the basics of the theory of quasimetric spaces to introduce a heuristic to such graphs,which is easy to calculate metric.The heuristic we obtain is both admissible and consistent,which allows us to use it efficiently in A*search algorithms.The developed application can be used in studies into evacuation from hazardous areas.In this case,optimum calculative efficiency is achievable with a simultaneous reduction of calculation time(when compared to Dijkstra’s algorithm).Our application can be applied during the first stage,i.e.,prior to the occurrence of a disaster,since this is an appropriate time for preparation by planning,drilling,early warning,and designating the rescue services that are to participate in the following stages.展开更多
基金the National Science Centre in Poland,grant number 2018/29/B/HS4/01020o-funded under the framework of the subsidy for tertiary education,aimed at academies and universities which participated in the IDUB Contest(“Inicjatywa Doskona?o sci-Uczelnia Badawcza”)。
文摘In the paper we discuss and compare two commonly used methods of finding the shortest paths in networks,namely Dijkstra’s and A*algorithms.We compare their effectiveness in terms of traversing road network in circumstances that require swift decision making in the event of dynamically changing road conditions on the basis of studies conducted for evacuation plans.To build a proper model of such a network,a method of appropriate edge-weighting is introduced,based on empirical data collected by other researchers.Then,we use the basics of the theory of quasimetric spaces to introduce a heuristic to such graphs,which is easy to calculate metric.The heuristic we obtain is both admissible and consistent,which allows us to use it efficiently in A*search algorithms.The developed application can be used in studies into evacuation from hazardous areas.In this case,optimum calculative efficiency is achievable with a simultaneous reduction of calculation time(when compared to Dijkstra’s algorithm).Our application can be applied during the first stage,i.e.,prior to the occurrence of a disaster,since this is an appropriate time for preparation by planning,drilling,early warning,and designating the rescue services that are to participate in the following stages.
