# Priority Queue
During the Breadth-first-search (BFS), Berblom uses a priority queue to schedule exploration of the next node.
The priority queue has the structure of `<Certificate, NodePriority>` with `NodePriority` being a combination of `path_length` and `trust_amount`.
Since the algorithm is a (slightly guided) BFS, the `path_length` is the primary and most crucial decision criterion on which node should be explored next.
The `trust_amount` is only considered, when multiple nodes have the same `path_length`, and serves the purpose of exploring the "best" path first.
In theory, a BFS doesn't need a priority queue, as the path length increases monotonically during the exploration of the network, whilst there are only ever nodes with two different path length in the queue.
`X` and `X+1`. Once all nodes with `X` are processed, the first nodes with `X+1` will be explored, which then lead to the discovery and enqueueing of nodes with the path length of `X+2`.
However, since we're utilizing Ford-Fulkerson's methodology of reverse edges, this property no longer upholds.
When a reverse edge is used, the path length is **not necessarily monotonically increased**.
It can instead be set to a value that is **smaller** than the path length (the amount of hops) until that point.
As described in the [traversing reverse edges chapter](./003_Traversing_Reverse_Edges.md), the path length is set to the length of the path that **created that reverse edge**, and that previously found path might have found a much shorter path to this node.
To prevent inconsistencies in the network, once such a "shorter path" is found, that path must be explored first.
## Example
For brevity's sake, the binding `Target, target@foo.example` will be referred to as `Binding`.
The paths in the following examples are written from the binding towards the trust anchor, as this example focuses on issues during the discovery of the path.
Consider the following network. All delegations have an umlimited trust depth, as depth isn't important for the purpose of this example.
The very first found path is the shortest path with the highest trust: `Binding -> CM3 -> CM2 -> CM1 -> TA1`
This results in the following residual network, which now contains reverse edges between `CM3 -> CM2 -> CM1 -> TA`.
There are now two paths from `Binding` towards `TA1`:
- `Binding -> CB3 -> CB2 -> CB1 -> CM1 ~~> CM2 -> CT2 -> CT1 -> TA1`
- `Binding -> CT5 -> CT4 -> CT3 -> CT2 -> CT1 -> TA1`
Now let's start another round of path search.
Below you see the state of the network after all nodes up to 5 hops away from `Binding` have been explored.
The top (blue) path simply followed forward edges and ended up with a path length of `5`.
The bottom (red) path however, followed forward bindings up to `CM1` with a path length of `4`, before taking a reverse edge, which set the path length on `CM2` to **2**! Taking that reverse edge effectively simulates that a trust amount of `10` is now rerouted via `CB3 -> CB2 -> CB1 -> CM1 -> TA1` and we're now looking for a new path from `CM3 -> CM2` forward.
This means that in the next iteration of the BFS, when `CM2` will be popped from the queue, it will find a shorter path with the length of `3` towards `CT2`, overwriting the path information from the previous path discovery by the top (blue) path.
**Without** a priority queue, the next node in the queue would be `CT1`, which would then discover `TA`, triggering the finalization process and the creation of a path with the trust amount of `30`.
During this process, the algorithm travels forward from `TA1` and hops along the path information on each node, subtracting the trust amount of `30` and creating reverse edges.
The algorithm would hop along `TA1 -> CT1 -> CT2`, before now taking a turn and hopping to `CM2`, which would crash, as we would try to subtract a amount of `30` from a delegation with an amount of `10`.
By introducing a `path_length` driven priority queue, the issue would already be solved at the fifth hop.
Once `CM2` is explored, its path length of `2` would push it to the top of queue, prioritizing the exploration from this node.
