โปรแกรมหาความยาวระหว่างสองเมืองในทางลัดใน Python

สมมติว่ามีเมืองจำนวน n และเมืองเชื่อมต่อกับถนนสองประเภท ทางหลวงและทางลัด ขณะนี้มีแผนที่และมีเพียงทางหลวงเท่านั้นที่ปรากฏบนแผนที่และไม่มีทางลัดทั้งหมด ฝ่ายขนส่งของเมืองต้องการเปิดระบบขนส่งที่เชื่อมระหว่างเมืองโดยใช้ทางหลวงและทางลัด เรารู้ว่ามีทางลัดระหว่างสองเมืองเมื่อไม่มีทางหลวงระหว่างพวกเขา งานของเราคือการหาระยะทางขั้นต่ำในแง่ของทางลัดจากเมืองเริ่มต้นไปยังเมืองอื่นๆ ทั้งหมด

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

และจุดยอดเริ่มต้นคือ 1 จากนั้นผลลัพธ์จะเป็น 3 1 2

ถ้าเราใช้แค่ทางลัด เส้นทางระหว่างเมือง 1 และ 2 จะเป็น 1->3->4->2 และค่าใช้จ่ายจะเป็น 3

ในทำนองเดียวกัน

1 และ 3:1->3 ราคา 1

1 และ 4:1->3->4 ราคา 2

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

• กราฟ :=รายการใหม่ที่มี n ชุด
• สำหรับแต่ละคู่ (x, y) ในขอบ ทำ
  • x :=x - 1
  • y :=y - 1
  • แทรก y ลงในกราฟ[x]
  • แทรก x ลงในกราฟ[y]
• temp_arr :=อาร์เรย์ใหม่ขนาด n ที่มีค่า -1
• b_set :=แผนที่ใหม่ที่มีคีย์ s - 1
• f :=ชุดใหม่ที่มีชุดความแตกต่างระหว่างตัวเลข 0 ถึง n และ b_set
• ดัชนี :=0
• ในขณะที่ขนาดของ b_set> 0, ทำ
  • สำหรับแต่ละองค์ประกอบ a ใน b_set ทำ
    • temp_arr[a] :=ดัชนี
  • nxt :=แผนที่ใหม่ที่มีค่าของกราฟที่ไม่ใช่ชุดย่อยของ b_set
  • f :=ตั้งค่าความแตกต่างของ f และ nxt
  • b_set :=nxt
  • ดัชนี :=ดัชนี + 1
• คืนค่าที่ไม่ใช่ศูนย์ของ temp_arr

ตัวอย่าง

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

def Solve(n, edge, s):graph =[set() for i in range(n)] สำหรับ (x, y) ในขอบ:x -=1 y -=1 graph[x].add (y) graph[y].add(x) temp_arr =[-1] * n b_set ={s - 1} f =set(range(n)).difference(b_set) index =0 while len(b_set)> 0:สำหรับ a ใน b_set:temp_arr[a] =index nxt ={f for f in f if not b_set.issubset(graph[f])} f =f.difference(nxt) b_set =nxt index +=1 return ( ' .join(str(t) สำหรับ t ใน temp_arr ถ้า t> 0)) พิมพ์(แก้(4, [(1, 2), (2, 3), (1, 4)], 1)) 
อินพุต
 
4, [(1, 2), (2, 3), (1, 4)], 1
 
ผลลัพธ์
 
3 1 2