Geoscience Reference
In-Depth Information
Fig. 2
Visual example
of the implementation of
cost adjustment in the least
risk path algorithm. The
underlined nodes
have
already been calculated and
selected.
Bold nodes
have
been calculated but not yet
selected. Nodes 1, 3 and 4
will be (re)calculated starting
in the selected node
Output:
Updated costs for endnodes of edges converging in the selected node
Calculate the number of edges leaving from selected node and select each edge
successively
Case a (Endnode of selected edge has not been selected):
• Calculate total risk values for endnode based on all possible routes arriving in
selected node
• Store the minimal value by comparing it with the currently stored value in
endnode
Case b (Endnode of selected edge has been selected BUT adjacent nodes have not
been selected):
• Calculate the number of edges leaving from endnode and select each edge
successively
• Calculate total risk values for endnode based on all possible routes arriving in
selected node and the connection between the selected node and its adjacent node
• Store the minimal value by comparing it with the currently stored value
Figure
2
shows that starting in the selected node, first Node 1 and Node 2 will be
checked. Node 1 has not yet been selected nor calculated (case a) and will be calcu-
lated as a path coming from selected node and its consecutive parent node. Node 2
has already been calculated and selected as next smallest cost node with a path con-
necting through its parent. When Node 2 was selected, Node 3 and Node 4 were
consecutively calculated with [Node 2—Parent of Node 2] as previous path nodes.
Although Node 3 and Node 4 were previously calculated with Node 2 as their
immediate parent node, the path coming from [Parent of Selected-Selected-Node 2]
could possibly be shorter than through [Parent of Node 2-Node 2]. This will be
checked through case b of the algorithm. This section also forms the increased com-
putational complexity compared to the Dijkstra shortest path algorithm.
For each path, the total length and risk values for the intermediate nodes are
calculated in both the shortest path and least risk path algorithm. Given the fact
that the only difference with the Dijkstra algorithm is in the cost calculation, and
there the additional calculations only affect the amount of edges in the selected
node, the computational complexity is similar to Dijkstra, being O(n
2
).
