title: Condition to terminate BFS
body: <p>I have this assignment where given a list of tuples where each tuple contains 2 Strings like this :</p>
  <ul>
  <li>[ (&quot;...&quot;,&quot;...&quot;) , (&quot;...&quot;,&quot;...&quot;) , (&quot;...&quot;,&quot;...&quot;) ... ]</li>
  </ul>
  <p>I have to calculate the <strong>shortest path</strong> which will lead to an <em>extreme-string</em>.</p>
  <p>An <em>extreme-string</em> is defined as a tuple of 2 strings where the first string is equal to the second string.</p>
  <p>I know this might sound confusing so let me set an example.</p>
  <p>Given :</p>
  <ul>
  <li>The list  [(&quot;0&quot;,&quot;100&quot;) , (&quot;01&quot;,&quot;00&quot;) , (&quot;110&quot;,&quot;11&quot;)]</li>
  <li>With indices 0,1,2</li>
  <li>The shortest path is : <strong>[2,1,2,0]</strong></li>
  <li>The <em>extreme-string</em> is equal to : &quot;110011100&quot;</li>
  </ul>
  <p>Step by step explanation :</p>
  <ul>
  <li><strong>Starting</strong> with tuple of index 2 the initial string is : &quot;110&quot;,&quot;11&quot;</li>
  <li><strong>Appending</strong> tuple of index 1 next string is : &quot;11001&quot;,&quot;1100&quot;</li>
  <li><strong>Appending</strong> tuple of index 2 next string is : &quot;11001110&quot;,&quot;110011&quot;</li>
  <li><strong>Appending</strong> tuple of index 0 final string is : &quot;110011100&quot;,&quot;110011100&quot;</li>
  </ul>
  <p>So say you begin with tuple (&quot;X&quot;,&quot;Y&quot;) and then you pick tuple (&quot;A&quot;,&quot;B&quot;) then result is (&quot;XA&quot;,&quot;YB&quot;).</p>
  <p>The way I approached this problem was using BFS <strong>which I already implemented</strong> and sounds right to me but there is an issue I am dealing with.</p>
  <p>If the input is something like :</p>
  <ul>
  <li>[(&quot;1&quot;,&quot;111&quot;)]</li>
  </ul>
  <p>then the <strong>algorithm will never terminate</strong> as it will always be in the state &quot;111...&quot; - &quot;111111111...&quot; .</p>
  <p>Checking for this specific input is not a good idea as there many inputs that can reproduce this result.</p>
  <p>Having an upper bound for the iterations is also not a good idea because in some cases a finite result may actually exist after the iterations bound.</p>
  <p>Any insight would be really useful.</p>