โปรแกรมค้นหาจำนวนเส้นทางที่จำกัดจากโหนดแรกถึงโหนดสุดท้ายใน Python

สมมติว่าเรามีกราฟเชื่อมต่อแบบถ่วงน้ำหนักแบบไม่ระบุทิศทางหนึ่งกราฟ กราฟมี n โหนด และมีป้ายกำกับตั้งแต่ 1 ถึง n เส้นทางตั้งแต่ต้นจนจบเป็นลำดับของโหนดเช่น [z0, z1, z2, ..., zk] ที่นี่ z0 คือโหนดเริ่มต้นและ zk เป็นโหนดปลายและมีขอบระหว่าง zi และ zi+1 โดยที่ 0 <=ผม <=k-1. ระยะทางของเส้นทางคือผลรวมของค่าน้ำหนักที่ขอบของเส้นทาง ให้ dist(x) หมายถึงระยะทางที่สั้นที่สุดจากโหนด n และโหนด x เส้นทางที่จำกัดเป็นเส้นทางพิเศษที่สอดคล้องกับ dist(zi)> dist(zi+1) โดยที่ 0 <=i <=k-1 ดังนั้น เราต้องหาจำนวนเส้นทางที่จำกัดจากโหนด 1 ถึงโหนด n หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนโมดูโลคำตอบ 10^9 + 7

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 3 เนื่องจากมีสามเส้นทางที่ถูกจำกัด (1,2,5), (1,2,3,5), (1,3,5)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• graph :=รายการที่อยู่ติดกันของกราฟที่สร้างจากรายการขอบที่กำหนด

• path :=อาร์เรย์ขนาด (n+1) และเติม 0

• เส้นทาง[n] :=1

• diss :=อาร์เรย์ขนาด (n+1) และเติมด้วย -1

• q :=คิวและแทรก (0, n) เริ่มต้น

• ในขณะที่ q ไม่ว่างให้ทำ

  • (dist, node) :=องค์ประกอบด้านหน้าของ q และลบออกจาก q

  • ถ้า diss[node] ไม่เหมือนกับ -1 แล้ว

    • ไปทำซ้ำต่อไป

  • dist[โหนด] :=dist

  • สำหรับแต่ละโหนดที่อยู่ติดกัน v และน้ำหนัก w ของกราฟ[โหนด] ให้ทำ

    • ถ้า diss[v] เหมือนกับ -1 แล้ว

      • แทรก (dist + w, v) ลงใน q

    • มิฉะนั้นเมื่อ diss[v]

      • เส้นทาง[โหนด] :=เส้นทาง[โหนด] + เส้นทาง[v]

  • ถ้าโหนดเหมือนกับ 1 แล้ว

    • เส้นทางกลับ[โหนด] mod 10^9+7

• คืนค่า 0

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

จากคอลเลกชัน นำเข้า defaultdictfrom heapq นำเข้า heappop, heappushdef แก้ปัญหา (n, ขอบ):กราฟ =defaultdict (dict) สำหรับคุณ, v, w ในขอบ:กราฟ[u][v] =w กราฟ[v][u] =w เส้นทาง =[0] * (n+1) เส้นทาง[n] =1 dist =[-1] * (n+1) q =[(0, n)] ขณะที่ q:dist, node =heappop(q ) if dists[node] !=-1:ดำเนินการต่อ diss[node] =dist สำหรับ v, w ใน graph[node].items():if dist[v] ==-1:heappush(q, (dist + w , v)) elif disists[v]  
อินพุต
 <ก่อนหน้า>5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5 ,1),(5,4,10)]

ผลลัพธ์

3