Shortest Path Between Connected Pairs Of Tuples

I'm new at this and i would be really greatfull for any kind of help...I have a list of tuples and I have to find shortest path between connected pairs of tuples. For example, I ha

Solution 1:

If you only search for the shortest path between two numbers (lets call them nodes) and the length of the edges between them is 1, you can use BFS, if they have some other distance, you can use Dijkstra. Since both are graph algorithms, you may need to change them a little since you have only a list of edges, not graph structure.

Solution 2:

Use BFS for solving a shortest path problem in an unweighted graph like that.

Pseudo code :

Create Queue q;
push into q starting node and mark distance to starting node as 0.
while(q is not empty){
 get n : first elemnt in the queue
 get all connected nodes to n that are not yet visited and push them to the queue:
 mark the distance to those node as the distance to n + 1.
}

Example : assuming your start node is 1.

connections you have in the graph :

   1->2,  1->3,  1->4
   2->1,  2->3,  2->4
   3->1,  3->2,  3->4

Set a visited array of boolean : visited 4 = {false,false,false,false}, and a distance array dist4 = {inf,inf,inf,inf} and parent array = {-1,-1,-1,-1}.

now push Node 1 into the queue Q, set it distance to 0 and parent to 1 then start:

Iteration 1 state:

Queue = {1}
Dist = {0,inf,inf,inf}
visited= {true,false,false,false}
parent= {1,-1,-1,-1}

Iteration 2 :

the only node in the Queue is 1, you pick it and push their neighbors to Queue which are nodes: 2,3,4. update their distances

Queue = {2,3,4}
Dist = {0,1,1,1}
visited= {true,false,false,false}
parent= {1,1,1,1}

and so on until you get an empty queue. (means you have visited all the nodes).

in this example you'll see that the distance to node 3 is Dist3 = 1, the parent of this node is parent3 = 1 (in case you want to reconstruct the path).

for more information check BFS and also an implementation in Python : Python BFS DFS or this

Solution 3:

def components_pairs(pairs):

    components = []

    for v1, v2 in pairs:
        for component in components:
             if v1 in component or v2 in component:
                 component.add(v1)
                 component.add(v2)
                 break
        else:
             components.append({v1, v2})

    return components

pairs = [(1,2),(1,3),(2,4),(3,1),(4,3)]

print(components_pairs(pairs))

Solution 4:

This is Travelling salesman problem. You can use genetic algorithm, it will goal a goal with the lowest cost of operations. Greetings.