Geology Reference
In-Depth Information
Fig. A2.4 An example of
undirected weighted graph
of order 6 and size 8
of intermediate nodes. This is a consequence
of the fact that in the case of weighted graphs
the distance between two adjacent nodes is not
anymore unity but it is given by the real-valued
measure ¢( x , y ). Consequently, the BFS algorithm
is not applicable to weighted graphs.
The following Dijkstra algorithm computes
the minimum distance between two nodes x and
y in a weighted graph. Let x be the starting node
and d ( x , z ) an ansatz about the distance of a vertex
z from x . The quantity d ( x , z ) will be updated
several times during the algorithm execution. At
any iteration, the algorithm of Dijkstra considers
a subset T of D , from which a node z having
minimum distance from x is selected. At this
point, for each element w in the neighborhood
of z and belonging to T , such that the distance
d ( x , w ) > d ( x , z ) C ¢( z , w ), the distance d ( x , w )is
set to d ( x , z ) C ¢( z , w ). Then, the algorithm up-
dates T by removing f z g and the operation is
repeated. The algorithm terminates when the se-
lected element of T coincides with y .If y cannot
be reached starting from x , the algorithm ter-
minates with d ( x , y ) D1 . The function select ()
called at step #1 is a simple linear search in T ,
which returns the first node in T having minimum
distance from x . The algorithm of Dijkstra is used
in seismic tomography and refraction seismology
to determine the best seismic ray path joining a
source to a receiver on the basis of a velocity
model. In fact, according to Fermat's principle,
the path taken between two points by a seis-
mic ray is the one that can be traversed in the
least time.
Algorithm A2.3 sp ( x , y ): Shortest path between
two nodes x and y (Dijkstra's algorithm).
Input: x , y 2 D
Output: d ( x , y ) 2<
f 0: d ( x , x ) 0; 8 y 2 D j y ¤ x , d ( x , y ) 1 ;
T D
1: z select ( T )
2: z D y ) stop
3: 8 w 2 I ( z ) j w 2 T , d ( x , w ) > d ( x , z ) C ¢ ( z , w )
) d ( x , w ) d ( x , z ) C ¢( z , w )
4: T T f z g
5: jump #1
g
Both the BFS and Dijkstra algorithms can be
used to test the connectivity of a data structure. A
graph G is connected if for each pair of nodes
x and y there exists a path joining them. An
alternative and widely used technique for deter-
mining graph connectivity is known as depth-
first search (DFS). In this approach, we start from
a node x 0 and visit an arbitrary element x 1 in
the neighborhood of x 0 . At this point, a node x 2
in the neighborhood of x 1 and not yet visited is
considered. Then, the algorithm proceeds through
a depth search, until a vertex x k is found, such
that the neighborhood I ( x k ) is empty or any node
in I ( x k ) has been already visited. Then, the depth
search restarts from x k 1 . When all the paths
rooted at x k 1 have been explored, the algorithm
restarts from x k 2 , and so on. Therefore, the
procedure alternates depth search with a back-
ward step, until the whole neighborhood of x 0
Search WWH ::




Custom Search