Dijkstra کے الگورتھم اور اس کے نفاذ

ریاضی اور کمپیوٹر سائنس میں نظریہ مخطط کے نام سے ایک علیحدہ علاقے ہے. اس سیٹ کے حصہ کے طور پر اور اس طرح کے vertices کے درمیان مختصر ترین راستہ تلاش کرنے کے مختلف مسائل کو حل کرنے کے لئے. اس مسئلہ کو حل کرنے کے ریاضی کے طریقوں میں سے ایک عام طویل ایک Dijkstra کے الگورتھم رہا ہے.

ایک حساب کا گراف کیا ہے

یہ خیال کیا جاتا ہے گراف کے تصور اٹھارویں صدی Leonardom Eylerom میں استعمال میں ڈال رہی ہے. کونگس کے سات پلوں - یہ جو کی تشکیل اور اس اصول کے کلاسیکی مسائل میں سے ایک کے حل کا اعلان کیا تھا. اس اصول کا مقصد اس بات کی وضاحت کرنے کے لئے اکثر مختلف شہروں کے درمیان تحریک کے طور پر اس قیاس کا استعمال کریں. اس کے بعد جہاز پر گراف ایک پورے روٹ vertices کے مخصوص اشیاء (جیسے شہروں)، اور کناروں بننے جہاں آریھ، ہو جائے گا - ایک راس سے دوسرے کو (شہروں کے درمیان ینالاگ سڑک) کا راستہ. Dijkstra کے الگورتھم، دیگر طریقوں کے علاوہ میں، اس مسئلے کا حل فراہم کر سکتے ہیں.

مختصر ترین راستہ تلاش کر رہا ہے

عام کاموں میں سے ایک گراف تھیوری اور اس کے آپ کو دو پوائنٹس کے درمیان زیادہ سے زیادہ قیمت کے راستے کا تعین کرنے کی ضرورت ہے جس میں سے ایک ہے. شہروں - - باہم پسلیاں ہیں، ایک ممکنہ سڑک ہے جو اس سے جس میں vertices کے گراف کے فیصلے کے طیارے کو کم کرنا ممکن ہے. ہر ایک سڑک کا اپنا لمبائی ہے، اس وجہ سے، اس پر سفر کچھ پیسہ خرچ کرنا پڑے گا. یہ وہ رقم ہے گراف میں کناروں کے وزن کے برابر ہے. ، ایک شہر سے راہ ہموار کرنے کا طریقہ سڑک اقل اسباب پر خرچ کیا جائے گا: پھر عملی طور پر مسئلہ ذیل کے طور پر تیار کیا جا سکتا ہے.

حل کرنے کے طریقوں

اس مسئلہ کو ہم بن وسیع پیمانے پر سائنسی دنیا میں نام سے جانا جاتا ہے کہ کچھ الگورتھم کی طرف سے ایجاد کیا گیا ہے کو حل کرنے کے لئے. مثال کے طور پر فلائڈ الگورتھم - Uorshella، فورڈ - Bellman. حل تلاش کرنے کے کلاسیکی طریقہ بھی Dijkstra کے الگورتھم ہے. اس بارت گراف کی (ہر کنارے کے نام سے جانا جاتا وزن) کے لئے استعمال کیا جا سکتا ہے، اور کمزور کرنے کے لئے. آپ کئی اقدامات کرنا ضروری حتمی طریقہ تلاش کرنے کے لئے.

Dijkstra کے الگورتھم

اس طریقہ کار کی بات یہ ہے کہ لاگت کی تمام اقمات،، دیا ایک ساتھ شروع ہے جس میں ہر ٹیگ ایک مخصوص قدر تفویض کیا جاتا ہے حقیقت میں ہے. پھر نتیجہ اقمات جن لیبلز کم سے کم ہیں شامل ہوں گے. سب سے پہلے ابتدائی قدم کے سب پھر 0. کی قیمت کے ساتھ ٹیگ کیا جائے گا، مندرجہ ذیل چوٹیوں کے تمام، یہ ہے کہ، ذریعہ سے پہنچا جا سکتا ہے کہ ان لوگوں کو سمجھا رہے ہیں. وہ لیبل لگا جس کی قدر راستوں کا سورس کوڈ اور وزن کی رقم کے طور پر مقرر کیا جاتا ہے کر رہے ہیں. چوٹیوں اگلے مرحلے کی، لیبل کے سب سے چھوٹی قدر ہے کہ ایک کو منتخب کریں اور یہ کہ اس سے ہم انٹرمیڈیٹ نوڈس استعمال کرتے ہوئے بغیر جا سکتے ہیں میں تمام اقمات کی تعلیم حاصل کی. ماخذ کوڈ کے علاوہ جس طرح کے وزن - ایک نیا لیبل لیبل چوٹیوں کے برابر کی وضاحت کریں. قدر سب سے لیبل سے کم ہے، تو لیبل تبدیل کر دیا جاتا ہے. دوسری صورت میں، یہ اصل قدر رہتا ہے. ایک الگ صف، جن کی جہت اقمات کی تعداد کے برابر ہے میں ایک ہی وقت میں، یہ اصلاح کے نتیجہ، جس کا ذخیرہ اور پرعزم انداز میں. جیسے Dijkstra کے الگورتھم ایک طریقہ کو لاگو کرنے کے لئے، پاسکل ایک بہت ہی آسان کا مطلب فراہم کرتا ہے. الگورتھم یہ آسانی سے ایک پروگرام کے ایک چھوٹے سائز ہے اس کے لئے بنیاد ہو سکتا ہے کہ فائدہ ہے. ایسے سافٹ ویئر کی پیداوار کی مثالیں انٹرنیٹ پر تلاش کرنے کے لئے آسان.

DLE حل کے مختلف ٹولز آپ زیادہ سے زیادہ راہ تلاش کرنے کے لئے کام کر سکتے ہیں. جیسے Dijkstra کے الگورتھم کے حل کے لئے، Delphi کے بصری ڈیٹا کی ان پٹ اور آؤٹ پٹ حتمی نتیجہ کا آسان شکل پیدا کر دے گا.