CSC-SY

من عنده أفكار عن حل الطلبات الثلاثة الأخيرة في السؤال الثاني من وظيفة الخوارزميات 2 الاولى(دمشق) ..
(مسألة أقصر طريق في بيان).

أنا عندي الحل بس ما عم احسن اكتبه هنا لأنه عم يطلع الكود مخربط
شو الطريقة ليطلع بشكل واضح :

أخي رأفت اذا بدك تكتب كود فاختار code من القائمة..

أما بانسبة للحل فبسم الله...
هناك ثلاث مسائل في هذه المسألة:
i. إيجاد أقصر طريق بين عقدتين(عقدة و عقدة).
ii. إيجاد أقصر طريق بين عقدة و كل العقد.
iii. إيجاد أقصر طريق بين كل عقدتين في بيان.
سنقوم برد الحالتين الأولى و الثالثة الى الحالة الثانية ...
عندما نريد الحصول على أقصر طريق بين عقدة و كل العقد .. يعني اننا سنقوم ببناء شجرة معممة .. تمثل شجرة أقصر الطرق و سيكون جذر الشجرة هو S العقدة المراد معرفة طرقها القصرى...
سنمثل الشجرة على شكل مصفوفتين :

a.	p:array[1..n]of integer 
b.	d:array[1..n]of integer 

حيث تمثل d مصفوفة الكلف ,,, فـd[i] تمثل أقل كلفة للانتقال من s إلى i
و تمثل p مصفوفة الاباء ,, فعندما نقول p[i]=j فهذا يعني أن أب العقدة I هو j , و عندما نريد معرفة أقصر طريق بين s و عقدة I نقوم بمعرفة الأب الأول لـi ثم جدها ثم جد أبوها ثم جد جدها حتى نصل إلى عقدة لا أب لها وهي عقدة البداية s ..

اذا كان البيان لا حلقي :
سنطبق خوارزمية bellman الصغيرة و التي تنص على التالي :
--------نفرز البيان طبولوجياً...
--------ثم أقوم ببناء شجرة أقصر الطرق , و ذلك عن طريق تكرار عملية الرخي relaxing عدد من المرات و بترتيب معين(سنتكلم عن عملية الرخي لاحقا).

سأقوم بالمشي على العقد المرتبة طبولوجياً واحدة تلو الأخرى (من البداية s إلى ما قبل النهاية)
و من أجل كل جارة من جارات العقدة الحالية سنقوم بمقارنة كلفة الوصول الحالية للعقدة الحالية + كلفة الرابط بين العقدة الحالية و الجارة الحالية فإذا كان الناتج أقل من الكلفة الحالية للجارة الحالية فهذا يعني أننا وجدنا طريق أقصر إلى الجارة الحالية يمر بالعقدة الحالية و عندها سنغير كلفة الوصول إلى الجارة الحالية( فيصبح : كلفة العقدة الحالية + كلفة الرابط مع الجارة المعنية) و أيضاً سنعدل على الطريق (الشجرة) فتصبح العقدة الحالية أباً للجارة الحالية(تسمى العملية السابقة بالرخي) . نتابع حتى ننتهي من كل جارات العقدة الحالية و من ثم نأخذ العقدة التالية(حسب الترتيب الطبولوجي) و نكرر السابق ... و هكذا حتى ننتهي من كل العقد .
و هذه اجرائية ال relaxing :

procedure relax(I,v:integer;var d,p:array-of-nodes)
begin
	if d[i]+W(I,v)<d[v] then
	begin
		p[v]:=I;
		d[v]:=d[i]+w(I,v);
	end;
end;

حيث تمثل w(i,j) كلفة الرابط من i الى j .
و ستصبح خوارزمية بناء شجرة الطرق القصرى (bellman ) كالتالي:

Type
Array-of-nodes=array[1..n]of integer;
Procedure Bellman(G:graph;var d,p:array-of nodes;toporder:array-of-nodes);
begin
d:={∞};
p:={nil};
d[t[1]]:=0;
for i:=t[1] to n-1 do
begin
for each vertex v adjacent to i do
relax(I,v,d,p);
end;
end;

حيث تمثل toporder مصفوفة الترتيب الطبولوجي للبيان الاحلقي..
و الآن لمعرفة أقصر طريق من s الى e نقوم بفرو البيان طبولوجياً:

T-Sort(G,t:)

و من ثم نستدعي خوارزمية bellman :

bellman(G,t;)

و لاستخلاص الطريق من s الى E :

I:=toporder[2];
J:=toporder[6];
If j<i then
Begin
	While not(i=j or p[i]=-1)do
	begin
		Push(s,p[i]);
		I:=p[i];
	End;
	If i=j then 
		Write-stack(s)
	Else
		Write('no way between j and i);
End
Else
	Write('no way between j and i);
End;

خوارزمية إيجاد الطريق الأقصر بين عقدة ما و بقية العقد الممكن الوصول إليها انطلاقاً من هذه العقدة:
شرح الخوارزمية:
نسجل زيارتنا للعنصر الحالي
ثم نضيف هذا العنصر إلى الطريق المسلوك حتى الآن ونضيف طول الطريق بينه وبين العنصر السابق إلى طول ذلك الطريق المسلوك
إذا لم نكون قد عدنا إلى عنصر الانطلاق تنفذ الخوارزمية ما يلي:
إذا كان الطريق المسلوك أصغر من آخر طريق مؤدي إلى العنصر الحالي احتفظنا به
أو أننا لم نكن قد احتفظنا بأي طريق مؤدي إلى العنصر الحالي :
نحفظ الطريق الحالي و طوله كأصغر طريق مؤدي أي العنصر الحالي مؤقتاً
ثم من أجل كل جوار للعنصر الحالي لم نزره من قبل نستدعي الإجرائية عودياً
شرط الاستدعاء:
تصفير طول الطريق المسلوك (temp.long)
ملء خانات مصفوفة الطريق المسلوك temp.path بـ -1 ما عدا الخانة الأولى بـ start
إسناد -1 لأطوال أقصر الطرق res[i].long←-1
ملء خانات مصفوفة الزيارات visited بالقيم المنطقية false
بالإضافة إلى تهيئة عناصر البيان

type
  MGraph=array[1..n,1..n]of integer;
  Visited=array[1..n]of boolean;
  ShortPath=record
    Path:array [1..n] of integer;
    long:integer;
  end;
  ShortPaths=array[1..n]of ShortPath;
procedure Short_Ways(mg:MGraph;curr:integer;v:Visited; temp:ShortPath; var res:ShortPaths);
  var i:integer;
  begin
    v[curr]:=true;
    i:=1;
    while temp.path[i]<>-1 do
      i:=i+1;
    temp.path[i]:=curr;
    temp.long:=temp.long+mg[temp.path[i-1],curr];
    if curr<>s then
      if (temp.long<res[curr].long) or (res[curr].long=-1)then
        begin
          res[curr]:=temp;
          for i:=1 to n do
            if ((mg[curr,i]<>-1)and(not v[i])) then
                short_ways(mg,i,v,temp,res);
        end;
  end;
الاستدعاء على الشكل :   
for i:=1 to n do
  if mg[s,i]<>-1 then
    short_ways (mg,i,v,temp,res);

شو مواصفات البيان الي بتشتغل معو خوارزميتك. .

بعدين , بهيك مسائل , الي متلي و متلك ما بيطلعلون يبتدعو حل لمسألة الطرق القصرى في بيان.
بيان لاحلقي : bellman الصغيرة .
بيان حلقي بأوزان موجبة : Dijkstra .
بيان حلقي و بأوزان سالبة :bellman-ford (و هي تخبرني بوجود حلقات ماصة في البيان).

و طبعاً يمكن حل الحالات الثلاثة السابقة كلها على bellman-ford .
مطوري هذه الخوارزميات علماء و فطاحل بالخوارزميات و خوارزمياتهم حالياً هي الTop في مسألة الطرق القصرى في بيان .

و هذه لقطة للسيد dijkstra المحترم :

اعتبرو يا أولي الالباب (Dijkstra)

يالله .. نبلش بالطلب الثالث..