a function to generate a path through a point and segment map. ps: complicated, at least for me

Question

Hello, I’m testing some ideas, doing some programs in python 3, and I need help with something complicated in which I don’t understand anything, nor can I come up with any viable solution. to summarize, I need to create a function which will receive 3 parameters (still to be discussed), and return me the shortest possible route between two plots.

to better understand how this function should work, I will demonstrate with an image. the image below.

as we can see, the image is composed of Balls and straight segments, think of each ball as a terrain, each has a unique code (ID so to speak) to be identified, this code is a string, can be a letter, name, Whatever it is, we should just note that it cannot contain a dot. or bar/ and will be a unique code for each land, not being able to have two land with the same code.

The land in turn, is linked by straight segments, think of them as roads, so we can think of routes as well. and that’s what I need, I need a function that will provide a stripe as the first parameter, this stripe will be a kind of map, I will provide the exit point as the second parameter, and the destination as the third parameter, it must return a string with the exit point route, up to the point of arrival, hence the need of the first parameter, as the map can change, we will always provide to the route calculator function, the updated map so that it can form and return the smallest possible route.

the first parameter it will receive will be a stripe full of string that identifies a route segment, a string that identifies a route segment is mounted as follows "ID1.ID2" the point is then used to separate ID1 from ID2 with the method . split(), both ID(s) in the case are land identifiers, previously mentioned, see for example in the image, the ground W is linked to the ground D, a string representing this in this case would be "W.D", the such stripe is nothing else than that, it has several strings inside that identify the routes and points together, a stripe that would serve as a parameter for this function, based on the image above would be as follows:

["O.H", "H.R", "E.Q", "G.A", "A.L", "K.A", "B.C", W.D, "J.I", "J.P", "M.E", etc etc...] is a general map summary

she must initially understand that there are the grounds, she must then extract them from the stripe she had received as parameter 1, that is, in the case of the map above, know that there are points A, B, C, D, E, F, G, H... sometimes they appear more than once in the stripes, for example, in the picture above, it is possible to see that the point E binds to more than one terrain, then it will appear more than once in the stripe ["E.H", "E.Q", "E.M", etc etc etc etc etc] when seen for the first time, the function can so to speak, "register it" and if seen later, can ignore while doing the first scan, it also depends on how it proceeds, can be otherwise, what we really want is, to pass a stripe that will be as described above, this parameter can be called Map, I will then pass two strings/parameters that will be the exit point and destination. let’s consider the photo above, we assume that we must start from point A and we must arrive at point E for the smallest possible route, we pass the exit point, the destination and the Map for the function, in this case we must return the string "A.E" that represents, translating to logical terms: We start in A, move from A to E, end. it returns the shortest possible route, now we assume that we want to leave A and reach point S, the function should return us the string "A.E.Q.S" which means: we start in A, move from A to E, move from E to Q, move from Q to S, end. note, although visually having segments larger than others, the smallest possible route only considers the number of lands we have to cross, if we leave from A to D, the shortest path would be "A.E.H.D", although there may also be the "A.E.Q.S.U.D" path, it is longer, therefore, worthless.

another observation is that there will be rare situations in which he will be able to identify two or more different routes but with equal distance, the function then will have to arbitrate choosing one of the routes to return, however can not be a random choice, imagine a case in a map where you go from a fictitious point P to a fictitious point C, the function arrives at two smallest possible routes as conclusion, the route ["P.Q.E.C"] and ["P.Q.F.C"] when I perform the calculation by calling the function N times, every time you have to return the same route, otherwise, time on the map will be drawn a route, time will be drawn another route between the grounds, would be strange, I do not know for sure how it would look to arbitrate between both routes, more could be done by some calculation, or alphabetical order. the first and the last point on both routes are equal, but the others are not, finally, while being provided the same map for the function, in these cases it should return the same answer always.

I would like an example of code, if possible, but more than that, an explanation of how this system works by calculating the smallest possible route. with such a function, I can even vary other functions such as getting a distance in numbers of segments from a point A to B, it is many more things, if you understand it in depth, I can do the opposite, create a function that returns the longest possible route or the number of possible different routes from point A to point B, interesting.

I do not consider myself a beginner but I am not professional, I managed to make a good dynamic inventory system, istanciable with ability to transfer item from one inventory to another, more garrei here, if you are reading so far, thanks for the attention.

Answer 1

mapa = {
     "1":"2345",
     "2":"134",
     "3":"124",
     "4":"123",
     "5":"1697",
     "6":"5g",
     "7":"508",
     "8":"07",
     "9":"5",
     "0":"87",
     "a":"bc",
     "b":"ac",
     "c":"abdg",
     "d":"ecf",
     "e":"d",
     "f":"d",
     "g":"6c",
     "h":"ij",
     "i":"hj",
     "j":"hik",
     "k":"j"}


def procurar(saida, destino, mapa):
    if len(saida) != len(set(saida)): return

    if saida[-1] == destino:
        print(saida)
        return 

    for i in mapa[saida[-1]]:
        procurar(saida+i, destino, mapa)

while True:   
     print()
     opc1 = input("--> saida: ")
     opc2 = input("--> destino:")
     print()

    if procurar(opc1, opc2, mapa) == None:
        print("erro, caminho não achado")

    else:
        print("SUCESSO")

I couldn’t get all the cute code in here, someone in the future if you want, you can edit it at will, thanks for the help.