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