المسار بين العقدتين

Question

أنا أستخدم NetworkX للعمل مع الرسوم البيانية. لدي رسم بياني كبير جدًا (إنه بالقرب من 200 عقد فيه) وأحاول العثور على جميع المسارات الممكنة بين العقدتين. ولكن ، كما أفهم ، يمكن لـ NetworkX العثور على أقصر مسار فقط. كيف يمكنني الحصول على أقصر مسار فقط ، ولكن كل المسارات الممكنة؟

تحديث: يمكن أن يحتوي المسار على كل عقدة مرة واحدة فقط.

UPD2: أنا بحاجة إلى شيء مثل Find_all_paths () ، الموضحة هنا: python.org/doc/essays/graphs.html لكن هذه الوظيفة لا تعمل بشكل جيد مع عدد كبير من العقد و deved = ((((

Answer 1

igraph, ، يمكن أن تحسب وحدة الرسم البياني الأخرى للبيثون كل أقصر المسارات بين زوج معين من العقد. إن حساب جميع المسارات لا يكون منطقيًا لأن لديك العديد من هذه المسارات بلا حدود.

مثال لحساب جميع أقصر المسارات من Vertex 0:

>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]

إذا كان لديك Igraph 0.6 أو أحدث (هذا هو إصدار التطوير في وقت كتابة هذا التقرير) ، يمكنك تقييد نتيجة get_all_shortest_paths إلى قمة نهاية معينة أيضًا:

>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
 [0, 1, 2, 12, 13, 14, 15],
 [0, 10, 11, 12, 13, 14, 15],
 [0, 1, 11, 12, 13, 14, 15],
 [0, 1, 2, 3, 13, 14, 15],
 [0, 1, 2, 3, 4, 5, 15]]

بالطبع عليك أن تكون حذرا ؛ على سبيل المثال ، افترض أن لديك رسم بياني شبكة 100 × 100 (يمكن إنشاؤه بسهولة Graph.Lattice([100, 100], circular=False) في igraph). إن عدد أقصر المسارات المؤدية من العقدة اليسرى العلوية إلى العقدة اليمنى السفلية يساوي عدد الاحتمالات لاختيار 100 عنصر من أصل 200 (دليل: طول أقصر مسار هناك 200 حواف ، سيذهب 100 منها "أفقيًا" في الشبكة و 100 منها سوف "عموديا"). ربما لا يتناسب هذا مع ذاكرتك ، وبالتالي حتى حساب كل أقصر المسارات بين هاتين العقدتين ليست ممكنة حقًا هنا.

إذا كنت بحاجة حقًا إلى جميع المسارات بين العقدتين ، فيمكنك إعادة كتابة الوظيفة المقدمة على صفحة الويب التي ذكرتها باستخدام Igraph ، والتي من المحتمل أن تكون أسرع من حل Python الخالص حيث يتم تنفيذ جوهر Igraph في C:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in set(graph.neighbors(start)) - set(path):
        paths.extend(find_all_paths(graph, node, end, path))
    return paths

يمكن تحسينه أكثر عن طريق تحويل الرسم البياني إلى تمثيل قائمة متاخمة أولاً لأنه سيوفر المكالمات المتكررة إلى graph.neighbors:

def find_all_paths(graph, start, end):
    def find_all_paths_aux(adjlist, start, end, path):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path))
        return paths

    adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
    return find_all_paths_aux(adjlist, start, end, [])

تعديل: مثال أول مثال على العمل في Igraph 0.5.3 أيضًا ، ليس فقط في Igraph 0.6.

Answer 2

يعمل هذا في الواقع مع NetworkX ، وهو غير مستقر ، والذي قد يكون لطيفًا للرسوم البيانية الكبيرة.

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths

Answer 3

ستجد خوارزمية Dijkstra أقصر مسار بطريقة مشابهة للبحث الأول عن العرض (يحل محل قائمة انتظار ذات أولوية موزونة بعمق في الرسم البياني لقائمة الانتظار الساذجة لـ BFS). يمكنك تمديده بشكل تافلي إلى حد ما لإنتاج مسارات 'n' أقصر إذا كنت بحاجة إلى عدد من البدائل ، على الرغم من أنك إذا كنت بحاجة إلى أن تكون المسارات مختلفة بشكل كبير (على سبيل المثال ، جدولة طرق شاحنات الأمان) ، فقد تحتاج إلى أن تكون أكثر ذكاءً في الاختيار المسارات التي تختلف بشكل كبير عن بعضها البعض.