(۳-۴)

با افزودن  به مسیر  به کوتاه‌ترین  مسیر می‌رسیم.
در هر مرحله کوتاه‌ترین مسیر‌ها بر روی هم، یک گراف همبند بدون دور را تشکیل می‌دهند که درخت نامیده می‌شود. بنابراین می‌توانیم این الگوریتم را یک فرایند «رشد یابنده درختی» به حساب آورده ، درخت نهایی، دارای این خاصیت است که برای هر راس  ، مسیر بین  کوتاه‌ترین  مسیر می‌باشد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

الگوریتم دایکسترا فقط فاصله بین  تا تمام راس‌های دیگر را تعیین می‌کند و خود کوتاه‌ترین مسیر‌ها را مشخص نمی‌نماید، به هرحال می‌توان این کوتاه‌ترین مسیرها را با نگهداری راس‌های سابق درخت و دنبال کردن آن‌ها، به راحتی به دست آورد.
الگوریتم دایکسترا نمونه‌ای ‌از آن چیزی است که ادمونذر آن را یک الگوریتم خوب نامیده است. یک الگوریتم نظریه گرافی، خوب است اگر تعداد مراحل محاسباتی مورد نیاز برای پیاده سازی آن روی هر گراف G از بالا توسط یک چند جمله‌ای ‌بر حسب  مثلاً  محدود شده باشد. یک الگوریتم که پیاده سازی آن ، نیازمند یک عدد نمایی از مراحل (مثلاً  )باشد. برای گراف‌های بزرگ بسیار غیر کارآمد خواهد بود.
برای اینکه نشان دهیم الگوریتم دایکسترا خوب است. دقت می‌کنیم که محاسبات انجام شده در کارهای ۲و۳ از نمودار گردشی ، روی هم رفته ، به  عمل جمع و   مقایسه نیازمندند. یکی از سوال‌هایی که در مورد این نمودار گردشی چندان دور از ذهن نسبت این است که چگونه می‌توان فهمید یک راس به  تعلق دارد یا خیر. دریفاس (در سال ۱۹۶۹) تکنیکی را برای انجام این کار ارائه داده که در مجموع به  مقایسه نیاز دارد. بنابراین اگر هر مقایسه یا عمل جمع را به عنوان یک واحد محاسباتی اصلی در نظر بگیریم، مجموع محاسبات مورد نیاز برای این الگوریتم تقریباً  بوده و در نتیجه از مرتبه  خواهد بود. (می‌گوئیم تابع  از مرتبه  است، اگر عدد ثابت مثبتی مانند c وجود داشته باشد. به طوری که به ازای هر  ،داشته باشیم:  .
گرچه مساله کوتاه‌ترین مسیر ، با یک الگوریتم خوب قابل حل است، ولی مسایل فراوان دیگری در نظریه گراف‌ها وجود دارند که هیچ الگوریتم خوبی برای آنها در دست نیست.
روند الگوریتم دیکسترا مطابق زیر می‌باشد :
۱- انتخاب راس مبدا
۲- مجموعه یS ، شامل رئوس گراف ، معین می‌شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه رئوسیکه کوتاه‌ترین مسیر به آن‌ها یافت شده است را در بر می‌گیرد.
۳- راس مبدا با اندیس صفر را در داخل S قرار می‌دهد.
۴- برای رئوس خارج از S ، اندیسی معادل ، طول یال + اندیس راس قبلی ، در نظر می‌گیرد . اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل ، می‌باشد.
۵- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعه یS اضافه می‌گردد.
۶- این کار را دوباره از مرحله‌ی ۴ ادامه داده تا راس مقصد وارد مجموعه یS شود.
در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده‌ی مسافت بین مبدا و مقصد می‌باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی‌باشد.
همچنین برای پیدا کردن مسیر می‌توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده‌ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه‌ترین مسیر بین دو نقطه نیز یافت می‌شود.
function Dijkstra(Graph, source):
dist[source] := 0 // Distance from source to source
for each vertex v in Graph: // Initializations
if v ≠ source
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
end if
add v to Q // All nodes initially in Q (unvisited nodes)
end for
while Q is not empty: // The main loop
u := vertex in Q with min dist[u] // Source node in first case
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] := alt
previous[v] := u
end if
end for
end while
return dist[], previous[]
end function
شکل ‏۳‑۱ الگوریتم دایکسترا.
شکل ‏۳‑۲ الگوریتم دیکسترا

الگوریتم‌ بلمن - فورد
الگوریتم بلمن-فورد الگوریتم پیمایش گراف است که مسئله کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌‌های وزن‌داری که وزن یال‌ها ممکن است منفی باشد حل می‌کند. الگوریتم دایکسترا مسئله مشابهی را در زمان اجرای کمترحل می‌کند، اما درآن الگوریتم می‌بایست وزن یال‌ها اعداد نامنفی باشند. بنابراین در عمل الگوریتم بلمن-فورد فقط برای گراف‌هایی که یال با وزن منفی دارند استفاده می‌شود. قبل از توضیح الگوریتم لازم به ذکر است که اگر گراف دوری با مجموع وزن منفی داشته باشد که از مبدأ قابل دست‌یابی باشد، مسئله کوتاه‌ترین مسیر جوابی نخواهد داشت، چرا که با پیمایش آن دور به هرتعداد بار دلخواه، مسیرهایی با وزن کمتر و کمتر حاصل خواهد شد. اجرای الگوریتم |v|-1 دنبالهd  چنان تعریف می‌شود که برای هر رأس v، مقدارdv  در پایان مرحله iام برابر وزن کوتاه‌ترین گذر از مبدأ بهv  است با این شرط اضافه که تعداد یال‌های این گذر حداکثرi باشد. بنابراین در پایان مرحله|v|-1 ام dv  برابر وزن کوتاه‌ترین مسیر از مبدأ بهv  خواهد بود.
نکته مهم : در واقع چون دور با مجموع وزن منفی نداریم، کوتاه‌ترین گذر با حداکثر |v|-1 یال از مبدأ به v، همان کوتاه‌ترین مسیر از مبدأ بهv  در گراف خواهد بود.
اساس کار الگوریتم، آزادسازی^[۴۱] همه یال‌های گراف در هر مرحله ‌است. آزادسازی یال (u,v)  به این معناست که اگر du + weight(u,v) < dv  آنگاه قرار می‌دهیمdu + weight(u,v) = dv . با این اوصاف اگر آزادسازی همه یال‌ها را برای بار |V|ام هم تکرار کنیم و بعد از این مرحله هم دنبالهd  تغییر کند، آنگاه می‌توان نتیجه گرفت که گراف دور منفی‌ای دارد که از مبدأ قابل دست‌یابی است. بنابراین الگوریتم بلمن-فورد توانایی تشخیص دور منفی را نیز دارد.
این الگوریتم نیز بسیار شبیه به الگوریتم دیکسترا بوده با این تفاوت که از یک راس شروع شده و به تمامی نقاط مجاور اندیس می‌دهد. با ادامه‌ی این روند و نگه داشتن اندیس‌های کوچکتر ، کوتاه‌ترین فاصله از راس مبدا به تمامی‌نقاط گراف محاسبه می‌شود و در نتیجه کوتاه‌ترین فاصله بین راس مبدا و مقصد نیز مشخص می‌گردد.
به مثال زیر توجه کنید: