-1
I need to store all possible routes to visit the vertices of a graph without going through the same vertex twice (TSP), I thought of generating the routes randomly and storing all that are not repeated.
Problem with this solution: I would not know when I have already found all the routes, not knowing so when to order the program to stop.
Any suggestions?
2
having the graph defined in the image
it has no restriction, I chose to use a dictionary (Vertice:exits) to represent it
grafo = {
'1' : '234',
'2' : '134',
'3' : '124',
'4' : '123',
}
found the use of recursion easier to solve
def acharCaminhos(caminho, meta, grafo):
way would be a string marking Vertice A
meta is Vertice B
graph is graph
if len(caminho) != len(set(caminho)): return
using Len and set I can tell if you have repeated vertical on the way
if caminho[-1] == meta:
print(caminho)
return
I check if the last Vertice on the way is the goal
for i in grafo[caminho[-1]]:
acharCaminhos(caminho+i, meta, grafo)
this looping recursiveness for all forks
Browser other questions tagged python algorithm graph
You are not signed in. Login or sign up in order to post.
That’s not exactly the question you asked in https://answall.com/q/426502/5878? What’s the difference?
– Woss
every fork in the graph is a list that symbolizes a path, not to repeat a Vertice just check if it is already in the list
– Elton Nunes
@Woss The previous question was closed because it is very comprehensive. I decided to ask a more specific question this time.
– Luiz Falcão
@Eltonnunes A friend told me the same thing, but I didn’t understand exactly how it works. Could you explain in more detail or show an example?
– Luiz Falcão
I think it’s still pretty wide. You can [Edit] and add your graph code, give an example of a few vertices and describe what would be the expected result for the example?
– Woss
Yeah, I’ll get ready here and post when I have an example
– Elton Nunes