Flooding and Flooding Distances

This chapter paves the way for many algorithms to construct dominated flooding. A flooding distance between nodes is defined as the lowest lake that contains two nodes. The shortest flooding distance to a node or a set of nodes is a valid flooding. Furthermore, dominated flooding may be expressed as the shortest flooding distance on an augmented graph, in which a dummy node and dummy edges encoding the ceiling function are introduced. The augmented graph enables us to devise several dominated flooding algorithms using popular shortest distance transforms. In particular, Dijkstra's shortest distance algorithm may be adapted to both node‐ and edge‐weighted graphs. Dijkstra's algorithm floods all the nodes in the increasing order of their flooding level. The core‐expanding algorithm on the contrary schedules the flooding in the increasing order of the flooding nodes and not of the flooded nodes.