Weighted Edit Distance: Cost Landscape & Alignment Path

Source / Target Strings

Source

Target

Edit Costs

Insertion cost 1.0

Deletion cost 1.0

Substitution cost 1.0

Result

Total edit cost

—

Operations

—

DP grid size

—

Op breakdown

—

How it works

For strings S (length m) and T (length n), the weighted edit-distance recurrence fills a DP table D of size (m+1)×(n+1):

D[i][0] = i · delCost
D[0][j] = j · insCost
D[i][j] = min(
  D[i-1][j]   + delCost,                      // delete S[i-1]
  D[i][j-1]   + insCost,                       // insert T[j-1]
  D[i-1][j-1] + (S[i-1]==T[j-1] ? 0 : subCost) // match / substitute
)
D[m][n] = minimum weighted edit distance

Each cell's fill colour encodes D[i][j] — the cheapest way to turn the first i characters of the source into the first j characters of the target. The table fills row by row, left to right, exactly in the order the recurrence requires each dependency to already be known. Once D[m][n] is reached, the glowing trace walks the actual backpointer chain from D[m][n] back to D[0][0]: the real sequence of inserts, deletes, substitutions (and matches) that achieves the minimum cost. Raising the deletion cost, for example, visibly pushes the optimal path away from delete-heavy routes toward insertions and substitutions instead — the whole heatmap and the recovered path reshape as the weights change.

Insertion / Deletion / Substitution sliders — recompute the whole DP table live with asymmetric operation costs.
Replay button — re-runs the animated cell-by-cell fill and the backtrace trace without changing any input.
Real-world relevance — this exact recurrence (with different cost weightings) powers spell-checkers, DNA/protein sequence alignment, plagiarism detection and fuzzy string matching.

Optimal alignment path DP cost cell (low → high)