เริ่มต้นใช้งานเริ่มต้นใช้งานได้ฟรี

เส้นทางที่สั้นที่สุด II

หลังจากเขียนโค้ดเพื่อตรวจสอบว่า destination node อยู่ใน neighbors หรือไม่แล้ว ขั้นต่อไปคือการขยายฟังก์ชันเดิมให้รองรับกรณีที่ destination node ไม่ได้ อยู่ใน neighbors

โค้ดทั้งหมดที่ต้องเขียนอยู่ในส่วนของเงื่อนไข else นั่นคือกรณีที่ node2 ไม่ได้ อยู่ใน neighbors

แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร

การวิเคราะห์เครือข่ายเบื้องต้นด้วย Python

ดูคอร์ส

คำแนะนำการฝึกหัด

  • ใช้เมธอด .add() เพื่อเพิ่ม node ปัจจุบัน node เข้าไปใน set visited_nodes เพื่อติดตามว่าได้เยี่ยมชม node ใดไปแล้วบ้าง
  • เพิ่ม neighbors ของ node ปัจจุบัน node ที่ยังไม่ได้ถูกเยี่ยมชมเข้าไปใน queue โดยใช้เมธอด .extend() ของ queue ร่วมกับ list comprehension ซึ่งเมธอด .extend() จะนำทุก item ใน list ที่กำหนดมาต่อท้าย
    • ทั้ง output expression และ iterator variable ของ list comprehension คือ n ส่วน iterable คือ iterator ของ neighbors และเงื่อนไขคือ n ต้อง ไม่อยู่ ใน visited nodes

แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ

ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์

def path_exists(G, node1, node2):
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    """
    visited_nodes = set()
    queue = [node1]

    for node in queue:
        neighbors = G.neighbors(node)
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True

        else:
            # Add current node to visited nodes
            ____

            # Add neighbors of current node that have not yet been visited
            queue.extend([____ for ____ in ____ if ____ not in ____])
แก้ไขและรันโค้ด