شناسایی دور
الگوریتم‌ها > الگوریتم فلوید

الگوریتم یافتن دور فلوید الگوریتمی است که از دو اشاره‌گر استفاده می‌کند، که با سرعت‌های متفاوت در دنباله حرکت می‌کنند. همچنین به نام «الگوریتم لاک‌پشت و خرگوش» نامیده می‌شود با اشاره به حکایت لاک‌پشت و خرگوش از ازوپ.
الگوریتم پس از نام رابرت فلوید با اعتبار اختراع آن توسط دانلد کنوت نام‌گذاری شد. با این حال به نظر نمی‌رسد این الگوریتم در کارهای منتشر شده از فلوید باشد، و این ممکن است یک سوءتفاهم باشد: فلوید توصیف الگوریتم را با لیست کردن تمامی دورها در یک گراف جهت دار سال ۱۹۶۷ سال در یک مقاله انجام داد، اما این مقاله مسئله یافتن دور در یک گراف تابعی که موضوع این مقاله است را شرح نداد. در واقع بیانیه کنوت (در سال ۱۹۶۹)، و نسبت دادن آن به فلوید، بدون استناد، اولین ظهور آن به‌طور چاپی است و آن را در نتیجه ممکن است یک قضیه منتسب به یک فرد است.
نکته اصلی در درک این الگوریتم این است که، برای هر عدد صحیح i ≥ μ و k ≥ ۰ داریم xi = xi + kλکه در آن λ طول حلقه یافت شده و μ اندیس اولین عنصر چرخه است. به‌طور خاص، i = kλ ≥ μاگر و تنها اگر xi = x2i. این الگوریتم تنها نیاز به بررسی مقادیر تکراری این فرم خاص، تا آنجا که یکی از مقادیر پس از شروع دنباله تکرار شود، برای یافتن دوره تناوبv برای تکرار که مضربی از λ می‌باشد. به محض اینکه v یافت شد، الگوریتم دنباله را دوباره از آغاز بررسی می‌کند تا اولین مقدار تکراری xμ، با توجه به این مسئله کهv بر λ بخشپزیر است به همین دلیل xμ = xμ + v. سرانجام پس از یافتن مقدار μ به‌طور بدیهی به دنبال طول λ می‌گردیم که کوچکترین طول دور می‌باشد، با یافتن اولین مکان μ + λ که در آن xμ + λ = xμ.
این الگوریتم در نتیجه دو اشاره گر را در طول دنباله داده شده حفظ می‌کند، یکی (لاک‌پشت) در xiو دیگری (خرگوش) در x2i. در هر مرحله از الگوریتم،i را با حرکت لاک‌پشت یک گام به جلو یک واحد افزایش می‌دهد و خرگوش دو گام به جلو در دنباله، و سپس مقدار دنباله در این دو اشاره گر را مقایسه می‌کند. کوچکترین مقدار i > 0 که در آن نقطه مقدار لاک‌پشت و خرگوش برابر است که مقدار ν مورد نظر ماست.
کد پایتون زیر این ایده به عنوان یک الگوریتم پیاده‌سازی می‌شود:
def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time,
    # and tortoise (reset to x0) moving towards the circle, will
    # intersect at the beginning of the circle. Because the
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1

    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1

    return lam, mu
این کد تنها به دنباله با ذخیره‌سازی و کپی کردن اشاره گرها، مقداریابی تابع و آزمون برابری دسترسی دارد؛ بنابراین، آن را به عنوان یک الگوریتم اشاره‌گری می‌نامیم. این الگوریتم از O(λ + μ) عملیات از این نوع و O(1) فضای ذخیره‌سازی استفاده می‌کند.