نشر توسط:admin Views 38 تاریخ : 2 خرداد 1395 نظرات ()
اگر تعداد گره ها زیاد باشد، الگوریتم فلوید کاراترست.اما اگر تعداد گره ها کم است، الگوریتم Dj بهتر کار می کند.
وجود چند دستور با مرتبه زمانی (O(1 در الگوریتم Dj باعث شده که در حالت گره های زیاد نتوان از آن ها چشم پوشی کرد.نتیجاً برای گراف هایی با گره های زیاد این الگوریتم کارایی خوبی ندارد.
از طرفی در الگوریتم فلوید چون در حلقه های for یالی که از یک گره به خود برمی گردد(loop)را هم بررسی می کنیم، زمانی را بیهوده مصرف کرده، و همین باعث شده که برای گراف هایی با یال های کم از الگوریتم فلوید استفاده نکنیم.
توجه کنید که در یک گراف با n گره در الگوریتم فلوید n مقایسه بیهوده(مقایسه یال کشیده شده از یک گره به خودش) با مرتبه ی زمانی(O(1 صورت می گیرد.
دو الگوریتم مرتبه زمانی یکسانی دارند ولی سرعت الگوریتم فلوید بیشتر است.
باز هم تاکید می کنم اگر مرتبه زمانی الگوریتم فلوید(O(n^3 است فقط به خاطر این است که برای هر جفت گره کوتاهترین مسیر مشخص می شود.