Geoscience Reference
In-Depth Information
5 Discussion and Conclusion
The presented modi
cation of the Dijkstra algorithm aims to provide better support
of decision making in situations where uncertainty of the data exists. It should be
helpful mainly by providing all solutions that can not be distinguished, or in other
words that have rather high similarity. This is archived by utilization of Fuzzy set
theory and Possibility theory to manage the uncertainty and the vagueness through
the calculation. The results obtained from the algorithm provide the user not only
with one optimal path but also with other options that are quite similar under the
given amount of uncertainty.
The use of fuzzy numbers as weights in the graph allows better modelling of the
real world situations where the time to travel from one point to another can not be
speci
ed exactly, or other similar cases. Specifying the time as a crisp number can
be too much idealization and simpli
cation of the problem, because the algorithms
for
finding optimal path then produce way to idealized solutions that do not take
into account either uncertainty or the amount of dissimilarity of the solutions.
The proposed algorithm proposes solution to both challenges, that were men-
tioned previously. It allows identi
cation of optimal path in uncertain environment.
This uncertain or vague environment is however better model of reality than exact
environment, where all the values are expected to be known precisely. The second
issue is addressed by providing not only one solution but a list of solutions. This
provides more alternatives that can be ranked using possibility and necessity
measures.
The variant of Dijkstra algorithm is in GIS also used for selecting least cost paths
on surfaces [
1
]. The proposed algorithm can be used for calculating optimal path on
surfaces that contain uncertainty, especially on so called fuzzy surfaces. Further
studies of the topic could be focus on this issue
—
selection of optimal paths on
fuzzy surfaces.
Acknowledgments The authors gratefully acknowledge the support by the Operational Program
Education for Competitiveness
—
European Social Fund (projects CZ.1.07/2.3.00/20.0170 and
CZ.1.07/2.2.00/28.0078 of the Ministry of Education, Youth and Sports of the Czech Republic).
References
1. Yu C, Lee J, Munro-Stasiuk MJ (2003) Extensions to least-cost path algorithms for roadway
planning. Int J Geogr Inf Sci 17(4):361
376
2. Mahdavi I, Nourifar R, Heidarzade A, Amiri NM (2009) A dynamic programming approach
for finding shortest chains in a fuzzy network. Appl Soft Comput 9(2):503
-
511
3. Okada S, Oper T (2000) A shortest path problem on a network with fuzzy arc lengths. Fuzzy
Sets Syst 109(1):129
-
140
4. Deng Y, Chen Y, Zhang Y, Mahadevan S (2012) Fuzzy Dijkstra algorithm for shortest path
problem under uncertain environment. Appl Soft Comput 12(3):1231
-
1237
-
Search WWH ::
Custom Search