باستخدام breadth_first_search الرسم البياني دفعة و() لإيجاد مسار في الرسم البياني صليات غير مرجح
-
22-07-2019 - |
سؤال
وأنا باستخدام الرسم البياني adjacency_list، مع حواف غير الموجهة وغير الموزونة. ولست بحاجة لإيجاد أقصر طريق بين قمة الرأس u و قمة ضد هل يجب استخدام breadth_first_search () بدءا من ش؟ عند الوصول إلى الخامس، كيف يمكنني الحصول على المسار، وكيف أتوقف عن البحث؟
وذلك بفضل!
المحلول
ويجب عليك استخدام واحدة من أقصر خوارزميات المسار، <وأ href = "http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/dijkstra_shortest_paths.html" يختلط = "نوفولو noreferrer" > ديكسترا أقصر مسار هي الأكثر مناسبة منذ كنت بحاجة إلى العثور على المسار بين الذروات اثنين فقط. هناك سبيل المثال ل ه الاستخدام في توزيع دفعة. هناك عدة خيارات للحصول على الناتج من تلك الوظيفة: إما عن طريق توفير خارطة الملكية المسافة أو بناء خريطة سلفه أو كتابة الزوار مخصص
.نصائح أخرى
نعم، لا breadth_first_search () بدءا من ش.
FOR every vertex i meet
IF i==v: BREAK
record predecessor of i as i.p
لإيجاد أقصر طريق، بدء من الخامس:
PRINT_PATH(u, v)
IF v==u
print u
ELSEIF v.p==NIL
print 'no path from u to v exists'
ELSE PRINT_PATH(u, v.p)
print v
وتحتاج إلى استخدام تمتد شجرة : خوارزمية البحث. هو الى حد بعيد بسيطة خوارزمية الجشع واضحة.