الگوریتم دیکسترا را چطور با لیست پیوندی می شه انجام داد
الگوریتم Dijkstra اون طور که تو کتاب CLRS اومده به این شکله:
کد:
DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S←∅
Q←V[G]
while Q≠∅
do {
u ← EXTRACT-MIN(Q)
S←S∪{u}
for each vertex v in Adj[u]
do RELAX(u,v,w)
}اگه منظورتون از "با استفاده از لیستهای پیوندی" استفاده از لیست مجاورتی برای نمایش گراف باشه، پیش فرض این الگوریتم تو این کتاب استفاده از لیست مجاورتیه.
کافیه آرایه ای به نام Adj به اندازه تعداد رئوس گراف در نظر بگیرید به طوری که عضو uام Adj لیستی از رئوس مجاور به رأس u باشند. مثلا اگر رأس ۲ با یالی به وزن ۳ به رأس ۴ و با یالی به وزن ۶ به رأس ۵ وصل باشه، لیست مربوط به رأس ۲ به این شکل می شه:
Adj[2]----><4, 3>----><5, 6>----->NIL
یعنی هر گره لیست، شامل شماره رأس، وزن یال متصل این رأس به رأس u و اشاره گری به رأس مجاور بعدیه.
روش کار الگوریتم هم اینه که ابتدا به رأس مبدأ مقدار صفر و به بقیه رأسها مقدار بی نهایت رو نسبت می ده (مقداردهی اولیه فاصله تخمینی). بعد تمام رأسها رو در صف اولویت مینیمم Q قرار می ده (با توجه به فاصله تخمینی) و یک به یک رأسی رو که فاصله براورد شده براش کمترین باشه رو از صف بیرون می کشه و تمام رأسهای مجاورش رو "آرامسازی" می کنه (یعنی اگه فاصله تخمینی با عبور از رأس u کمتر از فاصله تخمینی قبلی باشه، فاصله تخمینی رو اصلاح می کنه).
در خط for each باید روی همه رئوس لیست پیوندی رأس u حرکت بشه تا روشون آرامسازی انجام بشه.