Geoscience Reference
In-Depth Information
3 The Algorithm
The Dijkstra algorithm was proposed in 1959 [ 13 ] and it purpose is to identify
shortest path between given source node of the graph and all the other nodes. With
small modi
cation it can be also used to identify shortest path from starting node to
the destination node [ 4 ]. It is this variant of the algorithm which will be shown. The
algorithm is relatively simple and makes use of only two operations
addition and
comparison of crisp numbers. The algorithm works in several steps [ 4 ]:
1. assign all nodes distance value: zero for the starting node and in
nity for all
others
2. set all nodes as unvisited, set starting node as current
3. calculate cumulative distances from current node to all its neighbours, if the
distance is smaller then previously recorded distance then overwrite the distance
and write the previous node
4. set all neighbours of the current node as visited
5. move to next unvisited node
6.
if all the nodes were visited stop the algorithm.
The distance from one node to another is equal to the weight of the arc between
those nodes in the necessary direction. The distance of node Ni i from starting node is
equal to the sum of distances between those two nodes. For each node we store the
distance from the starting node and also the previous node on the path from starting
node. That way the shortest path from any node to the starting node can be iden-
ti
ed easily.
From the de
nition of the algorithm it is obvious that there is only one solution
to the problem of
finding optimal path between two nodes if such path exists.
However identi
cation of such ideal path is only possible in the environment
without uncertainty. As soon as uncertainty is introduced there maybe be several
solutions that can be hard or impossible to order. For the modi
ed version of
Dijkstra algorithm there is no assumption of one ideal path, in fact there is
assumption that several such paths exist and that there are differences that allow
their basic ordering.
There are several modi
cations to the algorithm. First is that all the weights in
graph are expected to be fuzzy numbers. The calculation on distances from starting
node to neighboring nodes is done according to decomposition theorem and Eq. ( 1 ).
The second change of the algorithm is that for each node the list of distances is
stored (Code Sample 1).
Search WWH ::




Custom Search