کمترین رستہ الخوارزم

اصطلاح	term
گراف راس کنارہ تیر لصق کمترین رستہ	graph vertex, vertices edge arc label shortest path

ریاضی کی شاخ نظریۂ گراف میں کسی موزون (وزن‌شدہ) گراف میں ایک قمہ سے کسی دوسرے قمہ تک کا کم ترین فاصلہ نکالنے کا الخوارزم۔ دو راس کے درمیان کمترین رستہ وہ ہو گا جب اس میں شامل کناورں کے وزنوں کی حاصل جمع تصغیر ہو۔

مثال

تصویر میں ہمیں قمہ S سے قمہ T تک کا کمترین فاصلہ نکالنا ہے۔ شروع قمہ S کو ہم صفر (0) جہد تفویض کرتے ہیں (تصویر میں جہد سرخ عدد سے دکھایا گیا ہے)۔ اب قمہ S سے راس A، B،اور، C تک پہنچنا ممکن ہے جن کا فاصلہ 9، 6 اور 12، ہے۔ ہم ان راس پر ان اعداد کے لصق عارضی طور پر لگاتے ہیں (تصویر (a) میں سبز رنگ سے یہ عدد دکھائے گئے ہیں)۔

اب ایسے راس جن میں سبز لصق لگے ہیں (تصویر (a))، ان میں سے B پر عدد 6 سب سے کم ہے، اس لیے اسے ہم B کا جہد قرار دے کر سرخ کر دیتے ہیں (تصویر (b))۔ قمہ B سے A، D، T، کو تیر جاتے ہیں، جن کے فاصلے 11، 8، 3، ہیں۔ ان فاصلوں کو ہم B کے جہد میں جمع کر کے A، D، T، پر عارضی 17، 14، 9، (سبز) لصق لگا دہتے ہیں (تصویر (b))۔

فائل:Shortest path algorithm depiction.png

تصویر (b) میں سبز لصق میں قمہ A پر 9 سب سے کم ہے، اس لیے ہم اسے A کا جہد قرار دے کر سرخ کر دیتے ہیں (تصویر (c))۔

اب ہم A سے شروع کرتے ہیں (تصویر (c))۔ قمہ A سے صرف قمہ D کو تیر جاتا ہے جس کا فاصلہ 4 ہے، جسے A کے جہد میں جمع کر کے D کا لصق 13 بنتا ہے۔ چونکہ 13 قمہ D پر پہلے سے موجود لصق 14 سے کم ہے، اس لیے ہم 14 کو مٹا کر D کا لصق 13 کر دیتے ہیں۔

اس عمل کو دہراتے ہیں جبتک ہمیں T کا جہد 15 حاصل ہو جاتا ہے (تصویر (f))۔ قمہ S سے قمہ T کا کمترین فاصلہ 15 ہے۔ غور کرو کہ تصویر (d) میں جب قمہ C کو جہد عطا کیا گیا تو قمہ T کا لصق 24 بنتا تھا مگر چونکہ یہ C پر پہلے سے موجود لصق 17 سے زیادہ تھا اس لیے C کے لصق کو تبدیل نہیں کیا گیا۔

کمترین رستہ ڈھونڈنے کے لیے ہم T سے واپس چلتے ہیں۔ قمہ T پر آنے والے تیروں میں سے قمہ D سے آنے والے تیر کا وزن برابر ہے T اور D کے جہد کے فرق کے، اس لیے ہم TD کو رستہ میں شامل کرتے ہیں (تصویر (f))۔ اس طریقہ سے ہمیں کمترین رستہ SADT معلوم ہوتا ہے۔

الخوارزم

وزن شدہ گراف کے قمہ S سے قمہ T تک کا کمترین فاصلہ نکالنے کے لیے:

• قمہ S کو صفر جہد تفویض کرو۔ جو قمہ S سے سیدھا پہنچا جا سکے اس قمہ پر S سے فاصلہ (وزن) کا لصق لگا دو۔ ان میں سے جو لصق سب سے چھوٹا ہو، اس کو ارتباطی قمہ کا جہد قرار دو۔
• جس قمہ (یا راس) کو ابھی جہد تفویض کیا ہے، اس طرح کے ہر قمہ V کے لیے، وہ راس W جو V سے سیدھے پہنچ جا سکیں پر لصق لگاؤ جو V کے جہد اور V سے W کے فاصلہ کی جمع ہو

(جہد V) + (فاصلہ V سے W)

بشرطیکہ یہ لصق W پر پہلے سے موجود (اگر موجود ہو) لصق سے چھوٹا ہو۔ جب ایسے تمام W پر یہ عمل کر لو، تو پھر گراف میں سب سے چھوٹا لصق ڈھونڈو (جو ابھی جہد قرار نہ دیا گیا ہو) اور ارتباطی قمہ (یا راس) پر لصق کو جہد بنا دو۔

• اُوپر والا قدم نئے جہد سے دہراؤ
• جب قمہ T کو جہد لگ جائے تو رُک جاؤ۔ یہ جہد S سے T تک کا کم ترین فاصلہ ہے۔
• کم ترین راستہ (یا رستے) T سے واپس جاتے ہوئے یوں نکالو۔ اگر تیر VW کے لیے

(جہد V) - (جہد W) = (فاصلہ V اور W کے درمیان)

تو تیر VW کو رستہ میں شامل کر لو۔

== مزید دیکھیے == == بیرونی روابط ==*

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات