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

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح 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 پڑھیٔے     ریاضی علامات