Изменения
→Алгоритм Вагнера — Фишера
Для нахождения кратчайшего расстояния необходимо вычислить матрицу <tex>D</tex>, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с <tex>1</tex>):
Псевдокод ниже решает простой частный случай, когда вставка символа, удаление символа и замена одного символа на другой стоят одинаково для любых символов.
<code>
'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2, '''int[]''' S2InsertCostInsertCost, '''int[]''' S1DeleteCostDeleteCost, '''int[]''' ReplaceCost):
D[0][0] = 0
'''fo'''r j = 1 '''to''' N
D[0][j] = D[0][j - 1] + S2InsertCost[j] InsertCost <font color=darkgreen>//S2InsertCost[j] - цена вставки символа S2[j]</font color=darkgreen>
'''for''' i = 1 '''to''' M
D[i][0] = D[i - 1][0] + S1DeleteCost[i] DeleteCost <font color=darkgreen>//S1DeleteCost[i] - цена удаления символа S1[i]</font color=darkgreen>
'''for''' j = 1 '''to''' N
'''if''' S1[i] != S2[j]
D[i][j] = min(D[i - 1][j] + S1DeleteCost[i]DeleteCost, D[i][j - 1] + S2InsertCost[j]InsertCost, D[i - 1][j - 1] + ReplaceCost[i][j]) <font color=darkgreen>//ReplaceCost[i][j] - цена замены символа S1[i] на символ S2[j]</font color=darkgreen>
'''else'''
D[i][j] = D[i - 1][j - 1]
