Geography Reference
In-Depth Information
Data
: G D .V; E/: a connected, simple, directed graph; G
0
D .E
0
;
E
/: the complete line
graph of G; o 2 E: the origin (starting) edge; I : a set of instructions;
w
W I !
R
C
:
the instruction weighting function; l W
E
! I
2
: the labeling function;
d W E I ! E [f
¿
g: the decision function;
v
W E E I !ftrue; falseg:the
chunk validity function.
Result
: Function p W E ! E I that stores for each edge the preceding edge and the
instruction used in the least cost path.
1 forall the
e 2 E
do
2
c.e/ 1;
/* Initialize cost function
c W E !
R
C
.*/
3
U
e
;;
/* Set that stores instruction, edge pairs. */
4
S fg;
/* Set of visited edges. */
5
c.o/D 0;
/* The cost to reach
o
is 0. */
6
p.o/ .o; i /;
/*
o
does not have a predecessor;
i
is arbitrary. */
// Process lowest cost edge until all edges are visited
7 while
jEnSj >0
do
8
e min.c.e/je 2 EnS/;
/* Find edge with minimal costs. */
9
S S [feg;
/* Add
e
to visited edges. */
forall the
e
0
2 EnS
such that
.e; e
0
/ 2
E
10
do
// Update instruction/edge pairs from
e
to
e
0
forall the
i 2 l.e; e
0
/
do
11
12
U
e
0
U
e
0
[f.i; e/g;
forall the
e
0
2 EnS
such that
.e; e
0
/ 2
E
do
// Update costs to
e
0
based on instruction weights
13
14
forall the
i 2 I
such that
d.i; e/D e
0
do
15
if
c.e
0
/>c.e/C
w
.i /
then
16
c.e
0
/ c.e/C
w
.i /;
17
p.e
0
/ .e; i /;
// Propagate instructions forward through the graph.
18
forall the
.i; e
p
/ 2 U
e
do
e
x
e
0
;
/* Start propagating at
e
0
.*/
19
20
X S [f
¿
g;
/*
X
is the set of all visited edges during propagation. */
21
while
e
x
62 X
do
22
X X [fe
x
g;
/* Add
e
x
to the visited edges. */
23
Set e
n
d.e
x
;i/;
/*
e
n
is the next edge from
e
x
reachable by instruction
i
.*/
if
e
n
¤
¿
then
24
25
U
e
n
U
e
n
[f.i; e
p
/g;
/* Add
.i; e
p
/
to the set of instructions of how to
reach
e
n
.*/
if
c.e
n
/>c.e
0
/^
v
.e
p
;e
n
;i/D
true
then
26
27
c.e
n
/ c.e
0
/;
/* Update the costs to reach
c
n
.*/
28
p.e
n
/ .e
p
;i/;
29
e
x
e
n
;
/* Continue propagation from
e
n
.*/
Search WWH ::
Custom Search