ค้นหาว่ามีเส้นทางที่มีความยาวมากกว่า k จากแหล่งที่มาใน C++ . หรือไม่

แนวคิด

ในส่วนที่เกี่ยวกับกราฟที่กำหนด จุดยอดต้นทางในกราฟและตัวเลข k (ในที่นี้ k จะระบุความยาวของเส้นทางของกราฟระหว่างจุดยอดต้นทางและจุดยอดปลายทาง) หน้าที่ของเราคือตรวจสอบว่ามีจุดเริ่มต้นอย่างง่าย (ไม่มีวงจร) หรือไม่ จากต้นทางที่กำหนดและสิ้นสุดที่จุดยอดอื่นใด (เช่น ปลายทาง) กราฟแสดงดังต่อไปนี้ -

อินพุต

Source s = 0, k = 64

ผลลัพธ์

True

มีเส้นทางง่ายๆ 0 -> 7 -> 1-> 2 -> 8 -> 6 -> 5 -> 3 -> 4 ซึ่งมีระยะทางรวม 68 กม. ซึ่งมากกว่า 64

อินพุต

Source s = 0, k = 70

ผลลัพธ์

False

ในกราฟด้านบน เส้นทางที่ง่ายที่สุดที่ยาวที่สุดคือระยะทาง 69 (0 -> 7 -> 1-> 2 -> 3 -> 4 -> 5-> 6 -> 8 ดังนั้นเอาต์พุตควรเป็นเท็จสำหรับอินพุตใดๆ ที่มากกว่า 69

วิธีการ

ควรสังเกตว่าสิ่งสำคัญอย่างหนึ่งคือเพียงแค่ดำเนินการ BFS(Breadth First Search) หรือ DFS(Depth First Search) และการเลือกขอบที่ยาวที่สุดในทุกขั้นตอนจะไม่ทำงาน เหตุผลเบื้องหลังขอบที่สั้นกว่าสามารถสร้างเส้นทางที่ยาวขึ้นได้เนื่องจาก ขอบน้ำหนักที่สูงขึ้นเชื่อมต่อผ่านมัน

ตอนนี้แนวคิดคือการนำ Backtracking มาใช้ ในกรณีนี้ เราเริ่มต้นจากแหล่งที่กำหนด ข้ามทุกวิถีทางจากจุดยอดปัจจุบัน ที่นี่ เราติดตามระยะทางปัจจุบันจากแหล่งที่มา จะเห็นได้ว่าถ้าระยะทางมากกว่า k เราคืนค่าเป็นจริง แต่ในกรณีทางเลือกอื่นเพื่อที่ว่าถ้าเส้นทางไม่ได้สร้างระยะทางเกิน k เราจะย้อนรอย

ทีนี้ก็เกิดคำถามขึ้นมาว่า เราจะแน่ใจได้อย่างไรว่าเส้นทางนั้นเรียบง่ายและไม่วนลูปเป็นวงจร? ในที่นี้ แนวคิดคือการติดตามจุดยอดเส้นทางปัจจุบันในอาร์เรย์ ในกรณีนี้ เมื่อใดก็ตามที่เราเพิ่มจุดยอดให้กับเส้นทาง เราจะตรวจสอบว่าจุดยอดมีอยู่แล้วหรือไม่อยู่ในเส้นทางปัจจุบัน เห็นว่าถ้ามีเราละเลยขอบ

ตัวอย่าง

// Program to find if there is a simple path with
// weight more than k
#include<bits/stdc++.h>
using namespace std;
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// Now this class represents a dipathted graph using
// adjacency list representation
class Graph{
   int V1; // Indicates no. of vertices
   // In this case, in a weighted graph, we need to store vertex
   // and weight pair for every edge
   list< pair<int, int>> *adj1;
   bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1);
public:
   Graph(int V1); // Shows constructor
   // Shows function to add an edge to graph
   void addEdge(int u1, int v1, int w1);
   bool pathMoreThanK(int src1, int k);
};
// Used to return true if graph has path more than k length
bool Graph::pathMoreThanK(int src1, int k){
   // Used to create a path array with nothing included
   // in path
   vector<bool> path1(V1, false);
   // Used to add source vertex to path
   path1[src1] = 1;
   return pathMoreThanKUtil(src1, k, path1);
}
// Used to print shortest paths from src to all other vertices
bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){
   // Now if k is 0 or negative, return true;
   if (k <= 0)
      return true;
   //Used to get all adjacent vertices of source vertex src and
   // recursively explore all paths from src.
   list<iPair>::iterator i;
   for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){
      // Used to get adjacent vertex and weight of edge
      int v1 = (*i).first;
      int w1 = (*i).second;
      // Now if vertex v is already there in path, then
      // there is a cycle (we ignore this edge)
      if (path1[v1] == true)
         continue;
      // Now if weight of is more than k, return true
      if (w1 >= k)
         return true;
      // Else add this vertex to path
      path1[v1] = true;
      // Now if this adjacent can provide a path longer
      // than k, return true.
      if (pathMoreThanKUtil(v1, k-w1, path1))
         return true;
      // Backtrack
      path1[v1] = false;
   }
   // Now if no adjacent could produce longer path, return
   // false
      return false;
}
// Used to allocates memory for adjacency list
Graph::Graph(int V1){
   this->V1 = V1;
   adj1 = new list<iPair> [V1];
}
//Shows utility function to an edge (u, v) of weight w
void Graph::addEdge(int u1, int v1, int w1){
   adj1[u1].push_back(make_pair(v1, w1));
   adj1[v1].push_back(make_pair(u1, w1));
}
// Driver program to test methods of graph class
int main(){
   // Used to create the graph given in above fugure
   int V1 = 9;
   Graph g(V1);
   // making above shown graph
   g.addEdge(0, 1, 5);
   g.addEdge(0, 7, 9);
   g.addEdge(1, 2, 9);
   g.addEdge(1, 7, 12);
   g.addEdge(2, 3, 8);
   g.addEdge(2, 8, 3);
   g.addEdge(2, 5, 10);
   g.addEdge(3, 4, 10);
   g.addEdge(3, 5, 15);
   g.addEdge(4, 5, 11);
   g.addEdge(5, 6, 3);
   g.addEdge(6, 7, 2);
   g.addEdge(6, 8, 7);
   g.addEdge(7, 8, 8);
   int src1 = 0;
   int k = 70;
   g.pathMoreThanK(src1, k)? cout << "Yes\n" :
   cout << "No\n";
   k = 68;
   g.pathMoreThanK(src1, k)? cout << "Yes\n" :
   cout << "No\n";
   return 0;
}

ผลลัพธ์

No
Yes