Zählen aller $\Delta$-optimalen Alignments

Als Notation bezeichnen wir mit $\Delta$-optimal alle Alignments, welche $\delta$-optimal für ein $\delta \leq \Delta$ sind.

Definition 6   Sei $N(v,\delta)$ die Anzahl der $\delta$-optimalen Pfade von s nach t, welche durch Knoten v laufen.

Wenn wir nun die Anzahl aller $\Delta$-optimalen Alignments wissen wollen, so interessieren wir uns für den Wert $\sum_{\delta \leq\Delta} N(t,\delta)$. Für ein festes $\delta$ berechnen wir diesen Wert, indem wir folgende Rekursion auflösen:

$$N(v,\delta) = \sum_{(u,v)\in E} N(u,\delta-\epsilon(u,v))$$

Das heißt, für jeden Knoten v berechnen wir $N(v,\delta)$ für alle $\delta$ mit $\delta=\delta '+\epsilon(u,v)$, wobei $N(u,\delta ')$ für einen Vorgänger u von v schon vorher berechnet wurde. In der Praxis muß man in jedem Knoten des Graphen die ensprechenden Werte für $\delta$ ablegen.