Изменения

* <tex>w(\epsilon, b)</tex> = <tex>1</tex>

* <tex>w(a, \epsilon)</tex> = <tex>1</tex>

Как частный случай, так и задачу для произвольных <tex>w</tex>, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все <tex>w</tex> неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ <tex>x</tex> на <tex>y</tex>, а потом с <tex>y</tex> на <tex>z</tex> не лучше, чем сразу <tex>x</tex> на <tex>z</tex>).