أقصر طريق في الخريطة

Question

لقد صممت رسم بياني مرجح باستخدام قائمة مجاورة طبيعية في MySQL. الآن أحتاج إلى العثور على أقصر مسار بين عقدين معينين.

لقد حاولت استخدام Dijkstra في PHP لكنني لم أستطع إمكانية تنفيذها (صعبة للغاية بالنسبة لي). مشكلة أخرى شعرت أنها كانت إذا كنت أستخدم Dijkstra، فستحتاج إلى النظر في كل العقد، وقد يكون ذلك غير فعال للغاية في رسم بياني كبير. لذلك يفعل أي شخص لديه رمز يتعلق بالمشكلة المذكورة أعلاه؟ سيكون من الرائع أن يظهر لي شخص ما على الأقل وسيلة لحل هذه المشكلة. لقد عالق هنا لمدة أسبوع تقريبا الآن. الرجاء المساعدة.

Answer 1

هذا يبدو وكأنه حالة كلاسيكية من خوارزمية A *، ولكن إذا لم تتمكن من تنفيذ Dijkstra، لا أستطيع رؤيتك تجتاحك *.

* على ويكيبيديا

تحرير: هذا يفترض أن لديك طريقة جيدة لتقدير (ولكن من الأهمية بمكان عدم التقدير) تكلفة الانتقال من عقدة واحدة إلى الهدف.

Edit2: أنت تواجه مشكلة في تمثيل قائمة المجاورة. يحدث لي أنه إذا قمت بإنشاء كائن لكل قمة في الخريطة، فيمكنك الارتباط مباشرة بهذه الكائنات عندما يكون هناك رابط. إذن ما لديك أساسا هو قائمة بالكائنات التي تحتوي كل منها على قائمة من المؤشرات (أو المراجع، إذا كنت كذلك) إلى العقد التي يجينونها. الآن، إذا كنت ترغب في الوصول إلى المسار لعقدة جديدة، فإنك تتبع الروابط فقط. تأكد من الحفاظ على قائمة بالمسارات التي تتبعها للحصول على قمة معينة لتجنب دورات لانهائية.

بقدر الاستئصال DB في كل مرة تحتاج إلى الوصول إلى شيء ما، ستحتاج إلى القيام بذلك على أي حال. أفضل أمل الخاص بك هو الاستعلام فقط DB عندما تحتاج إلى ... هذا يعني فقط الاستعلام عن ذلك فقط عندما تريد الحصول على معلومات على حافة معينة في الرسم البياني، أو لجميع الحواف من Vertext واحد في الرسم البياني (هذا الأخير من المحتمل كن طريقا أفضل) بحيث تضغط فقط على الإدخال / الإخراج ببطء مرة واحدة بدلا من القطاعات العملاقة في وقت واحد.

Answer 2

فيما يلي إصدار معرفة القراءة والكتابة من خوارزمية Dijkstra، في Java، قد يساعدك ذلك في معرفة كيفية تنفيذها في PHP.

http://en.literateprograms.org/dijkstra٪27s_algorithm_٪28Java٪29.

Answer 3

تقوم خوارزمية Dijkstra بإرجاع أقصر مسارات من Vertex إلى Vertexes الأخرى.
يمكنك العثور على رمز pseudo في ويكي.

لكنني أعتقد أنك بحاجة فلويد الخوارزمية التي تجد أقصر مسارات بين جميع الأدوات في معالجة موجهة.

التعقيد الرياضي كلاهما قريب جدا.

يمكن أن تجد لي تنفيذ PHP. من ويكي لكلا منهم.