Remove illegal edges from the permuation set (python)
<p>I am trying to apply brute-force method to find the shortest path between an origin and a destination node (OD pair). I create the network using networkX and call the permutations followed by the application of brute force. <br/>If all the nodes in the network are connected with all others, this is ok. But if some or many edges are not there, this method is not gonna work out.
To make it right, i should delete all the permuations which are containing the illegal edges. </p>

<p>For example if two permutation tuples are </p>

<blockquote>
  <p>[(1,2,3,4,5), (1,2,4,3,5)]</p>
</blockquote>

<p>and in my network no edge exist between node 2 and 3, the first tuple in the mentioned list should be deleted.</p>

<p><strong>First question</strong>: Is it an efficient way to first create permutations and then go in there and delete those containing illegal edges? if not what should I do?</p>

<p><strong>Second question</strong>: If yes, my strategy is that I am first creating a list of tuples containing all illegal edges from networkx "G.has_edge(u,v)" command and then going into the permutations and looking if such an edge exist, delete that permutation and so on. Is it a good strategy? if no, what else do you suggest.</p>

<p>Thank you :)</p>

<p>Exact solution for general TSP is recognized as non-polynomial. Enumerating all permutations, being the most straight-forward approach, is valid despite of its <code>O(n!)</code> complexity. Refer to <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow">wikipedia page of TSP</a> for more information. </p>

<p>As for your specific problem, generating valid permutation is possible using <a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">depth-first search</a> over the graph.</p>

<p>Python-like pseudo code showing this algorithm is as following:</p>

<pre><code>def dfs(vertex, visited):
    if vertex == target_vertex:
         visited.append(target_vertex)
         if visited != graph.vertices:
             return
         do_it(visited)     # visited is a valid permutation
    for i in graph.vertices:
        if not i in visited and graph.has_edge(vertex, i):
             dfs(i, visited + [i])

dfs(start_vertex, [start_vertex])
</code></pre>

python shortest-path brute-force