الگوریتم واگنر–فیشر
در علوم رایانه، الگوریتم واگنر-فیشر یک الگوریتم برنامه‌نویسی پویا می‌باشد، بدین معنا که در فرایند انجام محاسبه این فاصله، رشته‌ها به بخش‌های مختلف تقسیم شده و تغییرات به همراه وزن منحصربه‌فرد آن‌ها در آن بخش محاسبه می‌شود. این الگوریتم همانند روش «لونشتاین» دارای تغییرات درج حرف اضافه، حذف حرف اضافه و جایگزینی حرف می‌باشد؛ با این تفاوت که از لحاظ زمانی بهینه شده و برای تشخیص هر تغییر در رشته، هزینه‌های خاصی در نظر گرفته می‌شود و سپس، بهینه‌ترین مسیر برای دستیابی به جواب نهایی انتخاب می‌گردد. در موتورهای جستجو، پردازش کلمات و چک کننده‌های تلفظ از این الگوریتم استفاده می‌شود. این الگوریتم یکی از ساده‌ترین الگوریتم‌های خانواده ماشین الگوریتم حالت می‌باشد.
الگوریتم واگنر-فیشر دارای سابقه چندین اختراع است. لیستی از مخترعین این الگوریتم در زیر آمده‌است. البته این لیست کامل نمی‌باشد.
الگوریتم واگنر-فیشر فاصله ویرایشی را براساس اتخاذ یک ماتریس برای نگه‌داشتن فاصله‌های ویرایشی بین تمام پیشوندهای رشته اول و تمام پیشوندهای رشته دوم، محاسبه می‌کند؛ آنگاه مقادیر موجود در ماتریس را با پرکردن ماتریس محاسبه می‌کند، و در نتیجه فاصله بین دو رشته کامل را به عنوان مقدار نهایی به عنوان خروجی بازمی‌گرداند.
یک پیاده‌سازی ساده، به عنوان شبه‌کد برای تابع "LevenshteinDistance" که دو رشته را به عنوان ورودی می‌گیرد "(s به طول m و t به طول n)" و فاصله لوناشتاین (فاصله ویرایشی) بین آنها را محاسبه می‌کند، به صورت زیر است. توجه داشته‌باشید که رشته‌های ورودی تک اندیسی هستند، در حالی که ماتریس "d" دارای نمایه صفر است و codice_1 یک بازه بسته می‌باشد.  function LevenshteinDistance(char s[1..m], char t[1..n]):
فضای ناوردا در این الگوریتم این است که ما می‌توانیم بخش اولیه formula_1 را با استفاده از حداقل formula_2 عملیات formula_3 تغییر دهیم. در پایان، عنصر پایین-راست آرایه شامل پاسخ است.
def wagner_fischer_O1(s, t):
همان‌طور که قبلاً نیز اشاره شد، ناوردا (نامتغیر) این است که ما می‌توانیم با استفاده از حداقل formula_2 عملیات، بخش اولیه formula_1 به formula_3 تبدیل کنیم.
این مورد در ابتدا در سطر و ستون ۰ درست است زیرا formula_7 با انداختن تمام حروف i می‌تواند به یک رشته خالی formula_8 تبدیل شود. به‌طور مشابه، ما می‌توانیم formula_9 را به سادگی با اضافه کردن تمام حروف j، به formula_3 تغییر دهیم.
اگر formula_11، آن‌گاه ما می‌توانیم formula_12 را به formula_13 در k عملیات تغییر دهیم، آنگاه می‌توانیم همین کار روی formula_7 را انجام دهیم و فقط آخرین کاراکتر را رها کنیم، و k عملیات را انجام دهیم.
در غیر این‌صورت، فاصله، حداقلِ سه‌راه ممکن برای انجام این تغییر است:
اگر بتوانیم formula_1 را به formula_13 در k عملیات تبدیل کنیم، آن‌گاه به سادگی می‌توانیم formula_17 را برای بدست‌آوردن formula_3 در k + ۱ عملیات اضافه کنیم (درج).
اگر بتوانیم formula_1 را به formula_13 در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم formula_21 را حذف کنیم و سپس همان انتقال را با k + 1 عملیات انجام دهیم (حذف).
اگر بتوانیم formula_22 را به formula_13 در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم همان کار را روی formula_1 انجام دهیم و با k + 1 عملیات جای formula_21 را با formula_17 عوض کنیم (جانشینی).
عملیات‌های مورد نیاز برای تبدیل formula_1 به formula_3 عددی است که برای تبدیل همه sها به همه tها مورد نیاز است، و بنابراین formula_29 نتیجه نهایی ما می‌باشد.
این اثبات نمی‌تواند معتبر باشد چرا که تعداد قرار داده‌شده در formula_2 در واقع کمینه است؛ این کار برای نشان‌دادن دشوارتر است، و شامل یک مشاجره با تناقضی است که در آن فرض می‌کنیم formula_2 کوچک‌تر از حداقل سه است، و استفاده از این برای نشان‌دادن یکی از این سه مقدار، مقدار حداقل نیست.
محاسبه فاصله بین دو رشته MUSE و MUSIC. جواب نهایی در خانه آخر ماتریس (سطر ۷ ام و ستون ۶ ام) قرار دارد.
محاسبه فاصله بین دو رشته carnivore و herbivore.
یافتن فاصله بین دو رشته Saturday و Sunday.
یافتن فاصله بین دو رشته kitten و sitting. تغییرات احتمالی در این الگوریتم شامل موارد زیر است:برنامه‌نویسی پویا یک روش برنامه‌نویسی است که عمدتاً در برنامه‌نویسی رقابتی استفاده می‌شود. یکی از ساده‌ترین ترفندهای این متدولوژی، ذخیره‌سازی(Memorization) می‌باشد. ذخیره‌سازی(Memorization) یعنی مقادیری که در هر مرحله بدست می‌آوریم را در داخل یک آرایه ذخیره کرده و درصورت نیاز به چنین مقادیری، دوباره محاسبات مربوط به آن را انجام ندهیم. در این‌صورت سرعت برنامه افزایش می‌یابد. در الگوریتم واگنر-فیشر نیز از این روش استفاده می‌شود تا سرعت برنامه افزایش یابد. می‌توان گفت تفاوت روش واگنر-فیشر و لونشتاین، استفاده از برنامه‌نویسی پویا در الگوریتم واگنر-فیشر می‌باشد.
با مقداردهی اولیه ردیف اول ماتریس با صفر، ما یک متغیر از الگوریتم واگنر-فیشر را بدست می‌آوریم که می‌تواند برای جستجوی رشته‌ای فازی در یک رشته در یک متن استفاده شود. این تغییر، موقعیت نهایی انطباق متن را ایجاد می‌کند. برای تعیین موقعیت شروع رشته متناظر، تعداد درج و حذف‌ها را می‌توان به‌طور جداگانه ذخیره کرد و برای محاسبه موقعیت شروع از وضعیت نهایی استفاده کرد.
الگوریتم حاصل‌شده به هیچ وجه مؤثر نیست، اما در زمان انتشار آن(۱۹۸۰) یکی از اولین الگوریتم‌هایی بود که جستجوی تقریبی را انجام می‌داد.