โปรแกรม C ++ เพื่อค้นหาเส้นทางต้นทุนที่สั้นที่สุดในกราฟที่กำหนดสำหรับการสืบค้น q

สมมติว่าเราได้รับกราฟที่มีจุดยอด n จุดและมีการเชื่อมต่อน้อยที่สุด ขอบจะได้รับอาร์เรย์ที่เรากำหนดขอบในรูปแบบ {source, dest, weight} ตอนนี้ เราได้รับจำนวนการสืบค้น q โดยที่การสืบค้นแต่ละรายการอยู่ในรูปแบบ {แหล่งที่มา, ปลายทาง} เราต้องหาเส้นทางต้นทุนที่สั้นที่สุดจากต้นทางไปยังปลายทางผ่านจุดยอด k เราพิมพ์ต้นทุนของเส้นทางสำหรับการสืบค้นแต่ละครั้ง

ดังนั้น หากอินพุตเป็น n =6, q =3, k =1, edge ={{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5 , 3}, {5, 6, 2}}, การสืบค้น ={{1, 4}, {2, 6}, {2, 5}} จากนั้นผลลัพธ์จะเป็น 6 11 9

ขั้นตอน

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

กำหนดกราฟอาร์เรย์ 2 มิติของคู่ขนาด n * nกำหนดเส้นทางอาร์เรย์รวมของขนาด nกำหนดฟังก์ชัน dfs() ซึ่งจะใช้ a, b สำหรับแต่ละค่า i ที่ graph[a]:ถ้าค่าแรกของ i คือ เช่นเดียวกับ b แล้ว:ละเว้นส่วนต่อไปนี้ ข้ามไปที่การวนซ้ำถัดไป pathTotal[ค่าแรกของ i] :=pathTotal[a] + ค่าที่สองของ i dfs (ค่าแรกของ i, a) สำหรับการเริ่มต้น i :=0 เมื่อ i  
ตัวอย่าง
 

 ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
 
#include ใช้เนมสเปซ std;vector>> graph;vector pathTotal;int k;void dfs(int a, int b){ สำหรับ (auto i :graph.at(a)){ if(i.first ==b) ดำเนินการต่อ; pathTotal.at(i.first) =pathTotal.at(a) + i.second; dfs(i.first,a); }} โมฆะแก้ (int n, int q, vector> edge,vector> แบบสอบถาม){ int a, b, c, x, y; กราฟ.ปรับขนาด(n); pathTotal.resize(n); for(int i =0; i  (ขอบ[i]); b =รับ<1> (ขอบ[i]); c =รับ<2> (ขอบ[i]); ก--, ข--; graph.at(a).push_back(make_pair(b,c)); graph.at(b).push_back(make_pair(a,c)); } k--; dfs(k, k); for(int i =0; i > ขอบ ={{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6 , 2}}; vector> แบบสอบถาม ={{1, 4}, {2, 6}, {2, 5}}; แก้ (n, q, ขอบ, แบบสอบถาม); คืนค่า 0;}
 
อินพุต
 <ก่อนหน้า>6, 3, 1, {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}} , {{1, 4}, {2, 6}, {2, 5}}

ผลลัพธ์

6119