الگوريتم فلويد براي يافتن كوتاه ترين مسير

يك مشكل متداول در سفره هاي هوايي هنگامي كه پرواز مستقيم وجود نداشته باشد تعيين كوتاه ترين مسير پرواز از شهري به شهر ديگر است . حال الگوريتمي طراحي مي كنيم كه اين مسئله و مسائل مشابه را حل كند . نخست لازم است نظريه گراف ها را مرور كنيم . شكل يك گراف جهت دار و موضون را نشان مي دهد به خاطر داريد كه در نمايش تصويري گراف ها دايره نشان گر راس ها و خط ميان دو دايره نشان دهنده يال ها هستند . اگر هر يال داراي جهت باشد گراف را گراف جهت دار يا دياگراف مي گويند . هنگام رسم يال ها در اين گونه گراف ها از پيكان براي نشان دادن جهت استفاده مي كنيم در يك دياگراف بين دو راس امكان وجود دو يال است كه جهت آنها مخالف هم هست. براي مثال درشكل يك يال از v1 به v2 و يكي از v2 به v1