C++のソースからkを超える長さのパスがあるかどうかを確認します

コンセプト

与えられたグラフ、グラフ内のソース頂点、および数値k（ここでkは、ソース頂点と宛先頂点の間のグラフのパス長を示します）に関して、私たちのタスクは、開始する単純なパス（サイクルなし）があるかどうかを判断することです。指定されたソースから、他の頂点（つまり宛先）で終了します。グラフを以下に示します-

入力

Source s = 0, k = 64

出力

True

単純なパス0->7->1-> 2-> 8-> 6-> 5-> 3-> 4があり、合計距離は68 kmで、64を超えています。

入力

Source s = 0, k = 70

出力

False

上のグラフでは、最長の単純なパスの距離は69（0-> 7-> 1-> 2-> 3-> 4-> 5-> 6-> 8）であるため、69を超える入力の場合は出力がfalseになります。

メソッド

重要なことの1つは、BFS（幅優先探索）またはDFS（深さ優先探索）を実行するだけで、すべてのステップで最長のエッジを選択しても機能しないことに注意してください。理由は、エッジが短いとパスが長くなる可能性があるためです。それを介して接続されたより高いウェイトエッジ。

ここでのコンセプトは、バックトラッキングを実装することです。この場合、指定されたソースから開始します。現在の頂点からすべてのパスをトラバースします。ここでは、ソースからの現在の距離を追跡します。距離がkを超えると、trueが返されることがわかっています。ただし、代替手段の場合は、パスが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